从某本书上，我看到了一种做法，但是不是 2-SAT。

我把他的代码改编成了 2-SAT 的代码，如下：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll seed;
int randint(int l,int r){
	mt19937_64 rand(time(0) * ++seed);
	uniform_int_distribution<int> dis(l,r);
	return dis(rand);
}
const int N = 1e6 + 5;
int n,m,x[N];
struct node{int a,b,c,d;}a[N];
clock_t st,en;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(0));
	seed = rand() * (rand() & 1 ? 1 : -1) * rand();
	int cnt = 0;
	cin >> n >> m;
	for(int i = 1;i <= m;i++)cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
	for(int i = 1;i <= n;i++)x[i] = randint(0,1);
	while(true){
		int pos = -1;
		for(int i = 1;i <= m;i++){
			if(!(x[a[i].a] == a[i].b || x[a[i].c] == a[i].d)){pos = i;break;}
		}
		if(pos == -1){
			cout << "POSSIBLE\n";
			for(int i = 1;i <= n;i++)cout << x[i] << " ";
			return 0;
		}
		int tmp = randint(1,2) == 1 ? a[pos].a : a[pos].c;
		x[tmp] = !x[tmp];
	}
	cout << "IMPOSSIBLE";
}

对于测试点 P4782 #5，程序需要 291028 次才能找到方案。

猜想：

假如 $n,m\le10^4$，这个代码能否大概率 AC？

疑问：

这个代码在 $k$ 次随机中能找到正确分配方案的概率是多少？

tips：

1. 本人蒟蒻。

2. 代码乱写的。