前言
(2-SAT)的解法不止一种（例如暴搜？），但最高效的应该还是(Tarjan)。
说来其实我早就写过用(Tarjan)求解(2-SAT)的题目了（就是这道题：【2019.8.14 慈溪模拟赛 T2】黑心老板（gamble）），这篇博客本来已经石沉大海，打算坑掉了的，但由于在(CSP-S)前复习板子时忘记了这道题写法，结果板子题都挂了好几次，为了加深印象，为了自我惩罚，来补博客了。
基本模型
什么是(2-SAT)？
考虑有(n)个物品，每个物品有(0)和(1)两种取值。给出一些诸如第(i)个物品是(0/1)或第(j)个物品是(0/1)的限制，如：
- 第(1)个物品是(0)或第(2)个物品是(1)。
- 第(1)个物品是(1)或第(3)个物品是(1)。
- ......
而(2-SAT)，就是求出一个满足所有条件的可行解，或是判断无解。
建图
既然提到要用(Tarjan)了，那么首先我们需要把这个问题转移到图上。
我们把每个物品看作两个点，分别表示这个物品取(0)和取(1)。
由于题目中给出的限制不是很明确，所以我们要先将它进行转化。
例如，若题目中给出第(i)个物品是(x)或第(j)个物品是(y)。
那么如果第(i)个物品是(!x)，第(j)个物品就必须是(y)。反之，如果第(j)个物品是(!y)，第(i)个物品就必须是(x)。
即，将((i,!x))向((j,y))连边，((j,!y)) 向((i,x))连边。
求解
首先，我们考虑，如何判断已知的一组解(ans)的合法性。
不难发现，若能从((i,ans_i))走到((i,!ans_i))，就说明这组解是不合法的。
这无疑带给我们一些启发。
如果存在((i,0))与((i,1))能互相到达，那么就是无解的。否则一定有解。
结合强连通分量的概念，即若((i,0))与((i,1))在同一个强连通分量中，就无解。
然后我们要考虑如何找到一组可行解。
如果((i,0))所在的连通块能到达((i,1))，(i)就一定要选(1)，反之亦然。
而能到达，一个必要条件就是缩点后拓扑序较小。
而要比较拓扑序，实际上也可以直接比较所在连通块缩点后的编号，根据(Tarjan)的原理，显然编号越小拓扑序越大。
因此我们只要选择编号较小的方案即可。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000000
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
#define Gmin(x,y) (x>(y)&&(x=(y)))
using namespace std;
int n,m,ee,lnk[2*N+5];struct edge {int to,nxt;}e[2*N+5];
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define pc(c) (C==E&&(clear(),0),*C++=c)
#define tn (x<<3)+(x<<1)
#define D isdigit(c=tc())
int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];
public:
I FastIO() {A=B=FI,C=FO,E=FO+FS;}
Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
Tp I void write(Con Ty& x,Con char& y) {write(x),pc(y);}
I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}
}F;
namespace Tarjan//Tarjan缩点
{
int d,T,cnt,dfn[2*N+5],low[2*N+5],vis[2*N+5],S[2*N+5],col[2*N+5];
I void dfs(CI x,CI lst)//Tarjan
{
dfn[x]=low[x]=++d,vis[S[++T]=x]=1;
for(RI i=lnk[x];i;i=e[i].nxt)
!dfn[e[i].to]?(dfs(e[i].to,x),Gmin(low[x],low[e[i].to]))
:vis[e[i].to]&&Gmin(low[x],dfn[e[i].to]);
if(dfn[x]^low[x]) return;col[x]=++cnt,vis[x]=0;
W(S[T]^x) col[S[T]]=cnt,vis[S[T--]]=0;--T;
}
I void Solve()
{
RI i;for(i=1;i<=2*n;++i) !dfn[i]&&(dfs(i,0),0);//Tarjan
for(i=1;i<=n;++i) if(col[i]==col[n+i]) return (void)puts("IMPOSSIBLE");//判无解
for(puts("POSSIBLE"),i=1;i<=n;++i) F.write(col[i]>col[n+i],"
"[i==n]);//输出一组可行解
}
}
int main()
{
RI i,a,b,c,d;for(F.read(n),F.read(m),i=1;i<=m;++i)
F.read(a),F.read(b),F.read(c),F.read(d),add(a+n*(!b),c+n*d),add(c+n*(!d),a+n*b);//建边
return Tarjan::Solve(),F.clear(),0;
}