struct TwoSAT
{
    // maxn 为问题中涉及的变量的个数
    // 变量i  2*i表示i为假  2*i+1表示i为真
    // 每次调用千要先init()
    // 复杂度 O(m) m--边 字句个数
    int n, S[maxn<<1|1], c;
    vector<int> G[maxn<<1|1];
    bool mark[maxn<<1|1];
    void init(int n)
    {
        this->n = n;
        memset(mark, 0, sizeof(mark));
        for (int i=0; i<n+n; ++i)             G[i].clear();
    }
    // 加边  条件是 x=x_value or y=y_value
    void add_clause(int x, int x_value, int y, int y_value)
    {
        x = (x<<1) + x_value;
        y = (y<<1) + y_value;
        G[x^1].push_back(y);
        G[y^1].push_back(x);
    }
    bool solve()
    {
        for (int i=0; i<n+n; i+=2)
            if (!mark[i] && !mark[i+1])
            {
                c = 0;
                if (!dfs(i))
                {
                    while (c)       mark[S[--c]] = false;
                    if (!dfs(i+1))
                        return false;
                }
            }
        return true;
    }
    bool dfs(int x)
    {
        if (mark[x^1])              return false;
        if (mark[x])                        return true;
        mark[x] = true;
        S[c++] = x;
        for (int i=0; i<(int)G[x].size(); ++i)
            if (!dfs(G[x][i]))
                return false;
        return true;
    }