TWOSAT

struct twosat
{
    vector<vector<int>> adj, nadj, com;
    vector<bool> res, typ;
    vector<int> in, s;
    int n, l;
    twosat(int n = 0)
    {
        l = 0;
        this->n = n;
        adj.resize(n * 2);
        nadj.resize(n * 2);
        com.resize(n * 2 + 2);
        res.resize(n * 2);
        in.resize(n * 2);
        typ.resize(n * 2 + 2);
        s.reserve(n * 2);
    }

#define ID(x, t) ((t) ? (x) : (x) + n)

    void AddEdge(int u, bool typeu, int v, bool typev)
    {
        adj[ID(u, !typeu)].emplace_back(ID(v, typev));
        nadj[ID(v, typev)].emplace_back(ID(u, !typeu));
        adj[ID(v, !typev)].emplace_back(ID(u, typeu));
        nadj[ID(u, typeu)].emplace_back(ID(v, !typev));
    }
    void dfs(int v)
    {
        in[v] = 1;
        for (auto i : adj[v])
            if (!in[i])
                dfs(i);
        s.emplace_back(v);
    }
    void dfs_com(int v)
    {
        in[v] = l;
        com[l].emplace_back(v);
        for (auto i : nadj[v])
            if (!in[i])
                dfs_com(i);
    }
    void Kosaraju()
    {
        for (int i = 0; i < n * 2; ++i)
            if (!in[i])
                dfs(i);
        fill(in.begin(), in.end(), 0);
        while (s.size())
        {
            int c = s.back();
            s.pop_back();
            if (in[c])
                continue;
            ++l;
            dfs_com(c);
        }
    }
    void Trace()
    {
        for (int i = 1; i <= l; ++i)
        {
            for (auto j : com[i])
            {
                res[j] = typ[i];
                res[(j + n) % (n * 2)] = typ[in[(j + n) % (n * 2)]] = !typ[i];
            }
        }
    }
    bool sat()
    {
        Kosaraju();
        for (int i = 0; i < n; ++i)
            if (in[i] == in[i + n])
                return false;
        Trace();
        return true;
    }
};