回复即关

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+1;
int n,m,i,a,j,b,tim,tot,dfn[N],low[N],scc[N],instk[N];
vector<int> v[N],stk;
void tarjan(int x)
{
	dfn[x]=low[x]=++tim;
	stk.push_back(x);
	instk[x]=1;
	for(auto i:v[x])
	{
		if(!dfn[i])
		{
			tarjan(i);
			low[x]=min(low[x],low[i]);
		}
		if(instk[i])	low[x]=min(low[x],dfn[i]);
	}
	if(dfn[x]==low[x])
	{
		++tot;
		do
		{
			scc[x]=tot;
			x=stk.back();
			instk[x]=0;
			stk.pop_back();
		}
		while(low[x]!=dfn[x]);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>i>>a>>j>>b;
		v[i+n*a].push_back(j+n*(b^1));
		v[j+n*b].push_back(i+n*(a^1));
	}
	for(int i=1;i<=(n<<1);i++)	if(!dfn[i])	tarjan(i);
	for(int i=1;i<=n;i++)
		if(scc[i]==scc[i+n])
		{
			cout<<"IMPOSSIBLE";
			return 0;
		}
	cout<<"POSSIBLE\n";
	for(int i=1;i<=n;i++)	cout<<(scc[i]<scc[i+n])<<' ';
	return 0;
}