#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+
4;
int n,m,head[maxn<<
1],cnt=
0,dfn[maxn<<
1],low[maxn<<
1],vis[maxn<<
1],tim=
0,col[maxn<<
1],sum=
0;
struct node{
int to,next;
}e[maxn<<
1];
inline void add(
int u,
int v){
e[cnt].to=v;e[cnt].next=head[u];head[u]=cnt++
;
}
stack<
int>
s;
inline void tarjan(
int u){
dfn[u]=low[u]=++
tim;
vis[u]=
1;
s.push(u);
for(
int i=head[u];i!=-
1;i=
e[i].next){
int v=
e[i].to;
if(!
dfn[v]) {
tarjan(v);
low[u]=
min(low[v],low[u]);
}else if(vis[v]) low[u]=
min(low[u],dfn[v]);
}
if(dfn[u]==
low[u]){
col[u]=++
sum;
vis[u]=
0;
while(!
s.empty()){
int x=
s.top();s.pop();
if(x==u)
break;
col[x]=
sum;
vis[x]=
0;
}
}
}
int main(){
memset(head,-
1,
sizeof(head));
scanf("%d%d",&n,&
m);
for(
int i=
1;i<=m;i++
){
int x,a,y,b;scanf(
"%d%d%d%d",&x,&a,&y,&
b);
add(x+(!a)*n,y+b*
n);
add(y+(!b)*n,x+a*
n);
}
for(
int i=
1;i<=(n<<
1);i++
){
if(!
dfn[i]) tarjan(i);
}
for(
int i=
1;i<=n;i++
){
if(col[i]==col[i+
n]) {
cout<<
"IMPOSSIBLE";
return 0;
}
}
cout<<
"POSSIBLE"<<
endl;
for(
int i=
1;i<=n;i++
)
printf("%d ",col[i]>col[i+
n]);
}
转载于:https://www.cnblogs.com/wifimonster/p/10319900.html
