2-SAT でも解けます。 \(N\) 個の bool 変数に対して \(A_i\) 番目と \(B_i\) 番目は異なるという条件が \(M\) 個与えられることになります。

これは 2-SAT 上で \((x_{A_i}​ = 0)∨(x_{B_i} = 0), (x_{A_i}​ = 1)∨(x_{B_i} = 1)\) というクローズを足せば良いです。

計算量は \(O \left( N+M \right)\) です。実装は以下のリンクのように ACL を使うと簡単です。

実装例