An edge $$$(\lnot y, x)$$$ refers to the clause $$$(\lnot y \Rightarrow x)$$$.

$$$(x \lor y) \iff (y \lor x)$$$ (Commutative Property)
$$$(y \lor x) \iff (\lnot y \Rightarrow x)$$$ (Implication Law)

Finally, $$$(x \lor y) \iff ((\lnot x \Rightarrow y) \land (\lnot y \Rightarrow x))$$$.

struct two_sat {
    int n;
    vector<vector<int>> g, gr; // gr is the reversed graph
    vector<int> comp, topological_order, answer; // comp[v]: ID of the SCC containing node v
    vector<bool> vis;

    two_sat() {}

    two_sat(int _n) { init(_n); }

    void init(int _n) {
        n = _n;
        g.assign(2 * n, vector<int>());
        gr.assign(2 * n, vector<int>());
        comp.resize(2 * n);
        vis.resize(2 * n);
        answer.resize(2 * n);
    }

    void add_edge(int u, int v) {
        g[u].push_back(v);
        gr[v].push_back(u);
    }

    // For the following three functions
    // int x, bool val: if 'val' is true, we take the variable to be x. Otherwise we take it to be x's complement.

    // At least one of them is true
    void add_clause_or(int i, bool f, int j, bool g) {
        add_edge(i + (f ? n : 0), j + (g ? 0 : n));
        add_edge(j + (g ? n : 0), i + (f ? 0 : n));
    }

    // Only one of them is true
    void add_clause_xor(int i, bool f, int j, bool g) {
        add_clause_or(i, f, j, g);
        add_clause_or(i, !f, j, !g);
    }

    // Both of them have the same value
    void add_clause_and(int i, bool f, int j, bool g) {
        add_clause_xor(i, !f, j, g);
    }

    // Topological sort
    void dfs(int u) {
        vis[u] = true;

        for (const auto &v : g[u])
            if (!vis[v]) dfs(v);

        topological_order.push_back(u);
    }

    // Extracting strongly connected components
    void scc(int u, int id) {
        vis[u] = true;
        comp[u] = id;

        for (const auto &v : gr[u])
            if (!vis[v]) scc(v, id);
    }

    // Returns true if the given proposition is satisfiable and constructs a valid assignment
    bool satisfiable() {
        fill(vis.begin(), vis.end(), false);

        for (int i = 0; i < 2 * n; i++)
            if (!vis[i]) dfs(i);

        fill(vis.begin(), vis.end(), false);
        reverse(topological_order.begin(), topological_order.end());

        int id = 0;
        for (const auto &v : topological_order)
            if (!vis[v]) scc(v, id++);

        // Constructing the answer
        for (int i = 0; i < n; i++) {
            if (comp[i] == comp[i + n]) return false;
            answer[i] = (comp[i] > comp[i + n] ? 1 : 0);
        }

        return true;
    }
};

This problem is very direct. Each topping represents a variable. For a topping $$$x$$$ and preference '$$$+$$$', we use $$$x$$$ while adding a clause. For preference '$$$-$$$' we use $$$\lnot x$$$ in our clause.

#include <bits/stdc++.h>

using namespace std;

struct two_sat {
    int n;
    vector<vector<int>> g, gr;
    vector<int> comp, topological_order, answer;
    vector<bool> vis;

    two_sat() {}

    two_sat(int _n) { init(_n); }

    void init(int _n) {
        n = _n;
        g.assign(2 * n, vector<int>());
        gr.assign(2 * n, vector<int>());
        comp.resize(2 * n);
        vis.resize(2 * n);
        answer.resize(2 * n);
    }

    void add_edge(int u, int v) {
        g[u].push_back(v);
        gr[v].push_back(u);
    }

    // At least one of them is true
    void add_clause_or(int i, bool f, int j, bool g) {
        add_edge(i + (f ? n : 0), j + (g ? 0 : n));
        add_edge(j + (g ? n : 0), i + (f ? 0 : n));
    }

    // Only one of them is true
    void add_clause_xor(int i, bool f, int j, bool g) {
        add_clause_or(i, f, j, g);
        add_clause_or(i, !f, j, !g);
    }

    // Both of them have the same value
    void add_clause_and(int i, bool f, int j, bool g) {
        add_clause_xor(i, !f, j, g);
    }

    void dfs(int u) {
        vis[u] = true;

        for (const auto &v : g[u])
            if (!vis[v]) dfs(v);

        topological_order.push_back(u);
    }

    void scc(int u, int id) {
        vis[u] = true;
        comp[u] = id;

        for (const auto &v : gr[u])
            if (!vis[v]) scc(v, id);
    }

    bool satisfiable() {
        fill(vis.begin(), vis.end(), false);

        for (int i = 0; i < 2 * n; i++)
            if (!vis[i]) dfs(i);

        fill(vis.begin(), vis.end(), false);
        reverse(topological_order.begin(), topological_order.end());

        int id = 0;
        for (const auto &v : topological_order)
            if (!vis[v]) scc(v, id++);

        for (int i = 0; i < n; i++) {
            if (comp[i] == comp[i + n]) return false;
            answer[i] = (comp[i] > comp[i + n] ? 1 : 0);
        }

        return true;
    }
};

signed main() {
    int N, M;
    cin >> N >> M;

    two_sat solver(M);

    while (N--) {
        int topping1, topping2;
        char preference1, preference2;
        cin >> preference1 >> topping1 >> preference2 >> topping2;

        solver.add_clause_or(topping1 - 1, preference1 == '+', topping2 - 1, preference2 == '+');
    }

    if (!solver.satisfiable()) {
        cout << "IMPOSSIBLE";
        return 0;
    }

    for (int i = 0; i < M; i++)
        cout << (solver.answer[i] ? '+' : '-') << " ";
}

If $$$N$$$ was small enough, we could add constraints between each pair of cards. This would be $$$O(N^2)$$$. We cannot do that here.

For each integer $$$x$$$ from $$$1$$$ to $$$2N$$$, we want to store the indices of all the cards which have $$$x$$$ on any side, along with which side they have it on. Now our problem is the following: add implications in such a way that at most one card from each list is turned to the side which has that integer on it.

We can solve this problem for each list of indices separately. What all implications do we have? Let's consider a list $$$C$$$ of size $$$M$$$, for an arbitrary integer $$$x$$$. Let's make the use of $$$M$$$ additional variables $$$\it{pref}_i$$$ in our 2-SAT. $$$\it{pref}_i$$$ tells us if we have already displayed integer $$$x$$$ on a card in the range $$$[0, i - 1]$$$ of this list. We have the following logical implications:

1. If $$$C_i$$$ is $$$\it{true}$$$, $$$\it{pref}_{i + 1}$$$ must be $$$\it{true}$$$.
2. If $$$\it{pref}_i$$$ is $$$\it{true}$$$, $$$\it{pref}_{i + 1}$$$ must be $$$\it{true}$$$.
3. If $$$\it{pref}_i$$$ is $$$\it{true}$$$, $$$C_i$$$ must be $$$\it{false}$$$.

This way, we can solve this problem in linear time. See the code below to understand this better.

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int) (x).size()

struct two_sat {
    int n;
    vector<vector<int>> g, gr;
    vector<int> comp, topological_order, answer;
    vector<bool> vis;

    two_sat() {}

    two_sat(int _n) { init(_n); }

    void init(int _n) {
        n = _n;
        g.assign(2 * n, vector<int>());
        gr.assign(2 * n, vector<int>());
        comp.resize(2 * n);
        vis.resize(2 * n);
        answer.resize(2 * n);
    }

    void add_edge(int u, int v) {
        g[u].push_back(v);
        gr[v].push_back(u);
    }

    void add_edge(int i, bool f, int j, bool g) {
        add_edge(i + (f ? 0 : n), j + (g ? 0 : n));
        add_edge(j + (g ? n : 0), i + (f ? n : 0));
    }

    // At least one of them is true
    void add_clause_or(int i, bool f, int j, bool g) {
        add_edge(i + (f ? n : 0), j + (g ? 0 : n));
        add_edge(j + (g ? n : 0), i + (f ? 0 : n));
    }

    // Only one of them is true
    void add_clause_xor(int i, bool f, int j, bool g) {
        add_clause_or(i, f, j, g);
        add_clause_or(i, !f, j, !g);
    }

    // Both of them have the same value
    void add_clause_and(int i, bool f, int j, bool g) {
        add_clause_xor(i, !f, j, g);
    }

    void dfs(int u) {
        vis[u] = true;

        for (const auto &v : g[u])
            if (!vis[v]) dfs(v);

        topological_order.push_back(u);
    }

    void scc(int u, int id) {
        vis[u] = true;
        comp[u] = id;

        for (const auto &v : gr[u])
            if (!vis[v]) scc(v, id);
    }

    bool satisfiable() {
        fill(vis.begin(), vis.end(), false);

        for (int i = 0; i < 2 * n; i++)
            if (!vis[i]) dfs(i);

        fill(vis.begin(), vis.end(), false);
        reverse(topological_order.begin(), topological_order.end());

        int id = 0;
        for (const auto &v : topological_order)
            if (!vis[v]) scc(v, id++);

        for (int i = 0; i < n; i++) {
            if (comp[i] == comp[i + n]) return false;
            answer[i] = (comp[i] > comp[i + n] ? 1 : 0);
        }

        return true;
    }
};

const int MXN = 5e4 + 1, INF = 1e9 + 5;
two_sat solver;
vector<pair<int, int>> cards[2 * MXN];

void solve() {
    int N;
    cin >> N;

    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;

        cards[x].emplace_back(i, 1);
        cards[y].emplace_back(i, 0);
    }

    int use = N;

    solver.init(3 * N);

    for (int i = 0; i < 2 * N; i++) {
        if (cards[i].empty()) continue;

        for (int j = 0; j < sz(cards[i]); j++) {
            int cur = cards[i][j].first, val = cards[i][j].second;

            solver.add_edge(cur, val, use, 1); // If current true, prefix from next has to be true

            if (j > 0) { 
                solver.add_edge(use - 1, 1, cur, val ^ 1); // If prefix found, current cannot be true
                solver.add_edge(use - 1, 1, use, 1); // If prefix found, next prefix also true
            }

            use++;
        }
    }

    cout << (solver.satisfiable() ? "possible" : "impossible") << "\n";

    for (int i = 0; i < 2 * N; i++)
        cards[i].clear();
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    cin >> TC;
    while (TC--) solve();
}