如题

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <climits>
#include <cstdlib>
using namespace std;
#define int long long
#define inf 2147483647
#define maxn 2000010
int n,m,dfn[maxn],ins[maxn],low[maxn],bel[maxn],cnt,idx;
int head[maxn],nxt[maxn],to[maxn],tot; 
int st[maxn],top;
namespace Main{
	int rd(){
		int x=0,f=1;
		char ch=getchar();
		while(ch<'0'||ch>'9'){
			if(ch=='-'){
				f=-1;
			}
			ch=getchar();
		}
		while(ch>='0'&&ch<='9'){
			x=x*10+ch-'0';
			ch=getchar();
		}
		return x*f;
	}
	void wrt(int x){
		int y=10,len=1;
		if(x<0){
			x=-x;
			putchar('-');
		}
		while(y<=x){
			len++;
			y*=10;
		}
		while(len--){
			y/=10;
			putchar(x/y+'0');
			x%=y;
		}
	}
	int _min(int a,int b){
		return a<b? a:b;
	}
	void add(int u,int v){
		to[++tot]=v;
		nxt[tot]=head[u];
		head[u]=tot;
	}
	void dfs(int u){
		low[u]=dfn[u]=++idx;
		st[++top]=u;
		ins[u]=1;
		for(int i=head[u];i;i=nxt[i]){
			int v=to[i];
			if(!dfn[v]){
				dfs(v);
			}
			if(ins[v]){
				low[u]=_min(low[u],low[v]);
			}
		}
		if(low[u]==dfn[u]){
			cnt++;
			while(true){
				int v=st[top--];
				ins[v]=0;
				bel[v]=cnt;
				if(u==v){
					break;
				}
			}
		}
	}
	void main(){
		n=rd();
		m=rd();
		for(int i=1;i<=m;i++){
			int x=rd(),a=rd(),y=rd(),b=rd();
			add(x+n*(a&1),y+n*(b^1));
			add(y+n*(b&1),x+n*(a^1));
		}
		for(int i=1;i<=(n<<1);i++){
			if(!dfn[i]){
				dfs(i);
			}
		}
		for(int i=1;i<=n;i++){
			if(bel[i]==bel[i+n]){
				cout<<"IMPOSSIBLE";
				exit(0);
			}
		}
		cout<<"POSSIBLE"<<'\n';
		for(int i=1;i<=n;i++){
			wrt(bel[i]<bel[i+n]);
			putchar(' ');
		}
	}
}
signed main(){
	Main::main();
	return 0;
}