1.首先利用⇒(蕴含)将每一个子句$a∨b$改写成等价的$(¬a⇒b)∧(¬b⇒a)$。

可以给第 i个变量标号为 i，其对应的反值标号为i+n。

原式	建图
$¬a∨b$	$a→b∧¬b→¬a$
$a∨b$	$¬a→b∧¬b→a$
$¬a∨¬b$	$a→¬b∧b→¬a$

2.如果a点能够到达b点，就表示当a为真时b也为真。因此图中的同一个强联通分量中的所有布尔值均相同。也就是说，如果x与¬x在同一强连通分量内部，一定无解。反之，就一定有解了。

3.当x所在的强连通分量的拓扑序在¬x所在的强连通分量的拓扑序之后取x为真 就可以了。在使用Tarjan算法缩点找强连通分量的过程中，已经为每组强连通分量标记好顺序了。不过是反着的拓扑序。所以一定要写成$sccn[x]<sccn[-x]$。

时间复杂度：$O(N+M)$

模板：

有n个布尔变量$x_1～x_n$，另有m个需要满足的条件，每个条件的形式都是”$x_i$为true/false或$x_j$为true/false”。给每个变量赋值使得所有条件得到满足。

vector<int>v[2000010];
int dfn[2000010];//在DFS中该节点被搜索的次序
int low[2000010];//i或i的子树能够通过非树边追溯到最早的祖先节点（即DFS次序号最小）
int sccn[2000010];//缩点数组，表示某个点对应的强连通分量编号
bool vis[2000010];//是否在栈中
int step;
int cnt;//强连通分量编号
stack<int>s;
void tarjan(int u)
{
    dfn[u]=low[u]=++step;
    vis[u]=true;
    s.push(u);
    for(int i=0;i<v[u].size();i++)
    {
        int temp=v[u][i];
        if(!dfn[temp])//没有被访问过
        {
            tarjan(temp);
            low[u]=min(low[u],low[temp]);
        }
        else if(vis[temp])//在栈中
            low[u]=min(low[u],dfn[temp]);
    }
    if(low[u]==dfn[u])//构成强连通分量
    {
        cnt++;
        while(1)
        {
            int temp=s.top();
            s.pop();//此点以上的点全部出栈，构成一个强连通分量
            vis[temp]=false;
            sccn[temp]=cnt;//cnt是强连通分量的序号
            if(temp==u)break;
        }
    }
}
int main()
{
    int n,m,a,va,b,vb;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%d%d",&a,&va,&b,&vb);
        v[a+n*(va&1)].push_back(b+n*(vb^1));
        v[b+n*(vb&1)].push_back(a+n*(va^1));
    }
    step=cnt=0;
    memset(dfn,0,sizeof(dfn));
    memset(sccn,0,sizeof(sccn));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=2*n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
    {
        if(sccn[i]==sccn[i+n])
        {
            printf("IMPOSSIBLE\n");
            return 0;
        }
    }
    printf("POSSIBLE\n");
    for(int i=1;i<=n;i++)
        printf("%d ",sccn[i]<sccn[i+n]);
    printf("\n");
    return 0;
}