记录编号	206318	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的报告	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	0.163 s
提交时间	2015-11-06 17:16:14	内存使用	14.24 MiB

/*
Problem:cogs2100;
Language:c++;
by dydxh;
2015.11.06;
*/
#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<utility>
#include<ctime>
#include<cstdlib>
#include<string>
#define ll long long
#define ull unsigned long long
using namespace std;
const int maxn=200005;
const int oo=2000000000;
int n,m,len,cnt;
int linker[maxn],linkk[maxn],D[maxn];
struct edge{
	int y,next;
}er[maxn<<1],e[maxn<<1];
inline int read(){
	int x=0;bool flag=0;char ch=getchar();
	while(ch>'9' || ch<'0') {if(ch=='-') flag=1;ch=getchar();}
	while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return flag?-x:x;
}
void inserter(int a,int b){
	er[++len].next=linker[a];
	linker[a]=len;
	er[len].y=b;
}
void insert(int a,int b){
	e[++len].next=linkk[a];
	linkk[a]=len;
	e[len].y=b;
}
int Logo,Toper,cnt_Col;
int Dfn[maxn],Low[maxn],Sta[maxn],Col[maxn];
bool Ins[maxn];
void Tarjan(int x){
	Dfn[x]=Low[x]=++Logo;
	Ins[x]=true,Sta[++Toper]=x;
	for(int i=linker[x];i;i=er[i].next){
		int tn=er[i].y;
		if(!Dfn[tn]){
			Tarjan(tn);
			if(Low[tn]<Low[x])
				Low[x]=Low[tn];
		}
		else if(Ins[tn] && Dfn[tn]<Low[x])
			Low[x]=Dfn[tn];
	}
	if(Dfn[x]==Low[x]){
		++cnt_Col;int now=-1;
		while(now!=x){
			now=Sta[Toper--];
			Col[now]=cnt_Col;
			Ins[now]=false;
		}
	}
}
void dydxh_Build_Graph(){
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		if(x<0 && y<0){
			inserter(-2*y,-2*x-1);
			inserter(-2*x,-2*y-1);
		}
		else if(x>0 && y>0){
			inserter(2*x-1,2*y);
			inserter(2*y-1,2*x);
		}
		else if(x<0 && y>0){
			inserter(-2*x,2*y);
			inserter(2*y-1,-2*x-1);
		}
		else{
			inserter(-2*y,2*x);
			inserter(2*x-1,-2*y-1);
		}
	}
}
void dydxh_ReBuild(){
	for(int i=1;i<=cnt;i++){
		for(int j=linkk[i];j;j=e[j].next){
			int tn=e[j].y;
			if(Col[i]==Col[tn]) continue;
			insert(Col[tn],Col[i]);
			D[Col[i]]++;
		}
	}
}
int head,tail;
int Q[maxn],used[maxn],Op[maxn];
void dydxh_Top_Sort(){
	for(int i=1;i<=n;i++){
		Op[Col[i*2]]=Col[i*2-1];
		Op[Col[i*2-1]]=Col[i*2];
	}
	head=0,tail=0;
	for(int i=1;i<=cnt_Col;i++)
		if(!D[i])
			Q[++tail]=i;
	while(head<tail){
		int tn=Q[++head];
		if(used[tn]==0){
			used[tn]=1;
			used[Op[tn]]=-1;
		}
		for(int i=linkk[tn];i;i=e[i].next){
			int tmp=e[i].y;
			D[tmp]--;
			if(!D[tmp]) Q[++tail]=tmp;
		}
	}
}
int main(){
    freopen("asm_report.in","r",stdin);
    freopen("asm_report.out","w",stdout);
	n=read(),m=read(),cnt=2*n;
	dydxh_Build_Graph();
	for(int i=1;i<=cnt;i++)
		if(!Dfn[i])
			Tarjan(i);
	/*for(int i=1;i<=n;i++){
		if(Col[i*2]==Col[i*2-1]){
			printf("-1\n");
			return 0;
		}
	}*/
	dydxh_ReBuild();
	dydxh_Top_Sort();
	for(int i=1;i<n;i++){
		if(used[Col[i*2]]==1) printf("1 ");
		else printf("0 ");
	}
	if(used[Col[n*2]]==1) printf("1\n");
	else printf("0\n");
	//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
    return 0;
}