记录编号	154068	评测结果	AAAAAWAWAWWAAW
题目名称	[POI 2001] 和平委员会	最终得分	64
用户昵称	ztx	是否通过	未通过
代码语言	C++	运行时间	0.049 s
提交时间	2015-03-21 07:06:31	内存使用	4.54 MiB

/****************************************\
* Author : ztx
* Title  : [cogs] 313. [POI2001] 和平委员会
* ALG    : 2-SAT
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}

#define  maxe  80010LL
#define  maxn  50000LL

struct FST { int to , next ; } e[maxe] , e2[maxe] ;
int star[maxn] = {0} , tote = 1 ;
inline void AddEdge(int u , int v) { e[++tote].to = v ; e[tote].next = star[u] ; star[u] = tote ; }
int star2[maxn] = {0} , tote2 = 1 ;
inline void AddEdge2(int u , int v) { e2[++tote2].to = v ; e2[tote2].next = star2[u] ; star2[u] = tote2 ; }

int DFN[maxn] = {0} ;
int LOW[maxn] = {0} ;
int sta[maxn] = {0} , top = 0 ;
bool insta[maxn] = {0} ;
int belong[maxn] = {0} ;
int idx = 0 , cntblc = 0 ;

void dfs(int u) {
int v , p ;
	DFN[u] = LOW[u] = ++idx ;
	sta[++top] = u ; insta[u] = true ;
	for (p=star[u];p;p=e[p].next) {
		if (!DFN[v=e[p].to]) {
			dfs(v) ;
			if (LOW[u] > LOW[v]) LOW[u] = LOW[v] ;
		} else if (insta[v] && LOW[u]>DFN[v]) LOW[u] = DFN[v] ;
	}
	if (LOW[u] == DFN[u])
		for (cntblc++ ; u!=v ; ) {
			insta[v=sta[top]] = false ;
			belong[v] = cntblc ;
			top -- ;
		}
}

int q[maxe] ;
int head , rear ;
#define  push(x) q[++rear]=x
#define  pop() head++
#define  empty() (head>rear)
int visit[maxn] = {0} ;
int in[maxn] = {0} ;
int opp[maxn] = {0} ;

void Topo() {
int i , u , p ;
	head = 0 , rear = -1 ;
	Rep (i,1,cntblc) if (!in[i]) push(i) ;
	while (!empty()) {
		u = q[head] , pop() ;
		if (visit[u]) continue ;
		visit[u] = 1 , visit[opp[u]] = 2 ;
		for (p=star2[u];p;p=e2[p].next)
			if (!(--in[e2[p].to])) push(e2[p].to) ;
	}
}
///////////////////////spj
int map[500][500] = {0} ;
int ans[550] = {0} ;

int main() {
int n , m , i , u , v , p ;
	#define READ
	#ifdef  READ
		freopen("spo.in" ,"r",stdin ) ;
		freopen("spo.out","w",stdout) ;
	#endif
	read(n) , read(m) ;
	Rep (i,1,m) {
		read(u) , read(v) ;
		u -- , v -- ;
		if (n<250)map[u][v] = 1 ;
		if (u != (v^1)) {
//printf("Add %d %d\n",u,v^1);
//printf("Add %d %d\n",v,u^1);
			AddEdge(u,v^1) ,
			AddEdge(v,u^1) ;
		}
	}
	//Tarjan
	Rep (i,0,n*2-1)
		if (!DFN[i]) dfs(i) ;
	Rep (i,0,n-1) {
		if (belong[i<<1] == belong[i<<1|1]) {
			puts("NIE") ;
			goto END ;
		}
		opp[belong[i<<1]] = belong[i<<1|1] ;
		opp[belong[i<<1|1]] = belong[i<<1] ;
	}
	Rep (i,0,n*2-1) for (p=star[i];p;p=e[p].next) {
		if (belong[i] != belong[e[p].to]) {
			AddEdge2(belong[e[p].to],belong[i]) ;
			in[belong[i]] ++ ;
		}
	}
	Topo() ;
	Rep (i,0,n*2-1)
		if (visit[belong[i]] == 1) {
			//printf("%d\n", i+1) ;
if (n<250) ans[++ans[0]] = i ;
else printf("%d\n",i+1) ;
		}
if (n>=250) goto END ;
int j;
Rep (i,1,ans[0]-1)Rep (j,i+1,ans[0]) {
	if (map[ans[i]][ans[j]]) {
		puts(">_<") ;
		goto END ;
	}
}
Rep (i,1,ans[0]) printf("%d\n",ans[i]+1);
	END : ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}