<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

388. Soap Opera
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Brazil script writers are inexhaustible! Recently two greatest writers don Juan and donna Rosa have married. And now they are writing their shared scenario with a great happy end. So they want to maximize the amount of marriages at the end of the serial. In spite of their sympathy, Juan and Rosa have different points of view at the cinema, so there are some pairs of actors (of course, pair is a man and woman), such that Juan considers them photogenic, but Rosa does not and vise versa. In order to settle, newlyweds decided to select such a troup that both Juan and Rosa can combine marriages at the scenario in such a way that each actor will be married. You will be given the number of actors n and sets of successful pairs in the views of Juan and Rosa. Your task is to maximize the size of the troup.

Input
First line of the input file contains three integer numbers n, m1 and m2 — the number of actors, number of photogenic pairs in the views of Juan and Rosa respectively, 2 ≤ n ≤ 100. Each of the following m1 lines contains a pair of integer numbers between 1 and n — successful pair in the view of Juan. It is guaranteed that all Juan's pairs will be different. Next m2 lines describe Rosa's opinion in the same manner.

Output
In the first line output one integer number k — the maximal possible number of marriages at the end of the serial. Each of the following k lines should contain description of possible marriages in the view of Juan, and then output k lines — description in the view of Rosa.

Example(s)
sample input
sample output
4 2 2
1 3
2 4
1 4
2 3
2
1 3
2 4
3 2
4 1

<|response|>
## 1) Abridged problem statement

There are `n (2…100)` actors, each actor is either male or female (the overall graph is bipartite, though the partition is not given).
Juan approves `m1` pairs (edges `E1`), Rosa approves `m2` pairs (edges `E2`).

Choose the largest possible troupe (subset of actors) such that:

- Using only Juan's edges `E1`, all chosen actors can be perfectly paired into marriages.
- Using only Rosa's edges `E2`, the same chosen actors can also be perfectly paired.

Output `k` = maximum number of marriages, then print `k` Juan marriages and `k` Rosa marriages that realize it.

---

## 2) Detailed editorial

### Key reformulation

The union graph `E1 ∪ E2` is bipartite (guaranteed). Color it to get sides `A` and `B`.
Direct edges:
- Juan edges: `A → B`
- Rosa edges: `B → A`

A subset of actors supports perfect matchings in both `E1` and `E2` iff we can choose a vertex-disjoint set of directed cycles alternating Juan/Rosa edges. Each such cycle contributes one Juan match and one Rosa match on its vertices.

So the task becomes: maximize total vertices covered by vertex-disjoint alternating directed cycles.

### Reduction to min-cost circulation

Enforce "each actor used at most once" with node-splitting:
- Split actor `u` into `u_in` and `u_out` with edge `u_in → u_out`, capacity 1, cost 0.
- Relationship edges go `out → in`, capacity 1, cost -1 (profit for selecting them).

Find a **minimum-cost circulation**. It will send flow along negative cycles, selecting as many relationship edges as possible subject to vertex capacities. The network can have negative cycles (since we initialized all flows to 0 and only profit-edges are attractive), so a **network-simplex** style algorithm is used.

Each marriage contributes exactly two selected relationship edges (one Juan + one Rosa), so:

```
k = (-min_cost) / 2
```

Recover chosen marriages from relationship edges with flow > 0.

### Complexity

Node-split graph has `2n` nodes and `O(n^2)` edges. Network simplex runs in polynomial time.

---

## 3) C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/mincost_circulation.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<typename T>
class MinCostCirculation {
  private:
    struct Edge {
        int from, to;
        T capacity, cost, flow;
        Edge(int _from, int _to, T _capacity, T _cost, T _flow = 0)
            : from(_from),
              to(_to),
              capacity(_capacity),
              cost(_cost),
              flow(_flow) {}
    };

    int n;
    vector<Edge> edges;
    vector<int> pei, depth;
    vector<T> dual;
    vector<set<int>> tree;

    void dfs(int node) {
        for(auto ei: tree[node]) {
            if(ei == pei[node]) {
                continue;
            }
            int vec = edges[ei].to;
            dual[vec] = dual[node] + edges[ei].cost;
            pei[vec] = (ei ^ 1);
            depth[vec] = 1 + depth[node];
            dfs(vec);
        }
    }

    template<typename CB>
    void walk(int ei, CB&& cb) {
        cb(ei);
        int a = edges[ei].from, b = edges[ei].to;
        while(a != b) {
            if(depth[a] > depth[b]) {
                cb(pei[a] ^ 1), a = edges[pei[a]].to;
            } else {
                cb(pei[b]), b = edges[pei[b]].to;
            }
        }
    }

  public:
    MinCostCirculation(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        edges.clear();
        pei.assign(n + 1, -1);
        depth.assign(n + 1, 0);
        dual.assign(n + 1, 0);
        tree.assign(n + 1, set<int>());
    }

    int size() const { return n; }

    int add_edge(int from, int to, T capacity, T cost) {
        int id = edges.size();
        edges.push_back(Edge(from, to, capacity, cost, 0));
        edges.push_back(Edge(to, from, 0, -cost, 0));
        return id;
    }

    T min_circulation() {
        for(int i = 0; i < n; i++) {
            int ei = add_edge(n, i, 0, 0);
            tree[n].insert(ei);
            tree[i].insert(ei ^ 1);
        }

        T answer = 0;
        T flow;
        int cost, ein, eout, ptr = 0;
        const int B = 3 * n;
        for(int z = 0; z < (int)edges.size() / B + 1; z++) {
            if(!z) {
                dfs(n);
            }

            pair<T, int> pin = {0, -1};
            for(int t = 0; t < B; t++, (++ptr) %= (int)edges.size()) {
                auto& e = edges[ptr];
                if(e.flow < e.capacity) {
                    pin =
                        min(pin,
                            make_pair(dual[e.from] + e.cost - dual[e.to], ptr));
                }
            }

            tie(cost, ein) = pin;
            if(cost == 0) {
                continue;
            }

            pair<T, int> pout = {edges[ein].capacity - edges[ein].flow, ein};
            walk(ein, [&](int ei) {
                pout =
                    min(pout,
                        make_pair(edges[ei].capacity - edges[ei].flow, ei));
            });

            tie(flow, eout) = pout;
            walk(ein, [&](int ei) {
                edges[ei].flow += flow, edges[ei ^ 1].flow -= flow;
            });

            tree[edges[ein].from].insert(ein);
            tree[edges[ein].to].insert(ein ^ 1);
            tree[edges[eout].from].erase(eout);
            tree[edges[eout].to].erase(eout ^ 1);

            answer += flow * cost;
            z = -1;
        }
        return answer;
    }

    const Edge& get_edge(int id) const { return edges[id]; }
};

int n, m1, m2;
vector<vector<int>> G;

void read() {
    cin >> n >> m1 >> m2;
    G.assign(n, vector<int>(n, 0));
    for(int i = 0; i < m1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u][v] |= 1;
        G[v][u] |= 1;
    }
    for(int i = 0; i < m2; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u][v] |= 2;
        G[v][u] |= 2;
    }
}

void solve() {
    // This problem is conceptually not that hard - we are give two sets of
    // edges E1 and E2, and we want to find the largest subset of actors, such
    // that there is a perfect matching among both E1 and E2. One simplification
    // is that the problem has a "traditional" view and assumes the graph is
    // bipartite.
    // To solve this, one of the core ideas is that we can first colour the
    // nodes, and then direct the edges from Juan and Rosa in opposite
    // direction. Then selecting a subset of people is equivalent to selecting a
    // set of node disjoint cycles with the largest number of edges. We can
    // think of this as a circulation problem, but the tricky bit is that we are
    // interested in maximum so we will have negative cycles (as we need to
    // invert all weights). Classical algorithms unfortunately fail, so we
    // either need to go for cost scaling push relabel, or network simplex (or
    // some slower variants like cycle elimination). Personally, the network
    // simplex is the most intuitive and it's easier to implement so here we opt
    // for that.
    // It's unclear by the problem statement, so one thing we should make sure
    // is that the cycles don't have common nodes. An easy way to do this is to
    // split each node into two parts "u" and "u+n", with capacity 1 between
    // than and cost 0. Then all incoming edges will go to "u", while all
    // outgoing will come out of "u+n".
    // It might be good to read up on min circulation, as before this problem
    // I had incorrectly believed that a good chunk of flow implementations
    // actually work for negative cycles:
    //     - https://codeforces.com/blog/entry/104075?#comment-925064
    //     - https://codeforces.com/blog/entry/57018
    //     - https://codeforces.com/blog/entry/94190 (+ regular simplex)

    vector<int> color(n, -1);
    function<bool(int, int)> check_bipartite_dfs = [&](int u, int c) -> bool {
        color[u] = c;
        for(int v = 0; v < n; v++) {
            if(!G[u][v]) {
                continue;
            }
            if(color[v] == -1) {
                if(!check_bipartite_dfs(v, 1 - c)) {
                    return false;
                }
            } else if(color[v] == color[u]) {
                return false;
            }
        }
        return true;
    };

    for(int i = 0; i < n; i++) {
        if(color[i] == -1) {
            assert(check_bipartite_dfs(i, 0));
        }
    }

    MinCostCirculation<int64_t> mcc(2 * n);
    vector<tuple<int, int, int, int>> edge_info;

    for(int i = 0; i < n; i++) {
        mcc.add_edge(i, i + n, 1, 0);
        for(int j = i + 1; j < n; j++) {
            if(!G[i][j]) {
                continue;
            }

            // Juan edges: always go 0->1
            // Rosa edges: always go 1->0
            if(G[i][j] == 1 || G[i][j] == 3) {
                if(color[i] == 0 && color[j] == 1) {
                    int ei = mcc.add_edge(i + n, j, 1, -1);
                    edge_info.push_back({ei, i, j, 1});
                } else {
                    int ei = mcc.add_edge(j + n, i, 1, -1);
                    edge_info.push_back({ei, i, j, 1});
                }
            }
            if(G[i][j] == 2 || G[i][j] == 3) {
                if(color[i] == 1 && color[j] == 0) {
                    int ei = mcc.add_edge(i + n, j, 1, -1);
                    edge_info.push_back({ei, i, j, 2});
                } else {
                    int ei = mcc.add_edge(j + n, i, 1, -1);
                    edge_info.push_back({ei, i, j, 2});
                }
            }
        }
    }

    int ans = -mcc.min_circulation() / 2;

    vector<pair<int, int>> juan, rosa;
    for(auto [ei, u, v, type]: edge_info) {
        if(mcc.get_edge(ei).flow > 0) {
            if(type == 1) {
                juan.push_back({u, v});
            } else {
                rosa.push_back({u, v});
            }
        }
    }

    cout << ans << '\n';
    for(auto [u, v]: juan) {
        cout << u + 1 << ' ' << v + 1 << '\n';
    }
    for(auto [u, v]: rosa) {
        cout << u + 1 << ' ' << v + 1 << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4) Python solution (same idea, cycle-canceling min-cost circulation)

```python
import sys

# -------------- Min-Cost Circulation via Negative-Cycle Cancelling --------------

class Edge:
    __slots__ = ("to", "rev", "cap", "cost")
    def __init__(self, to, rev, cap, cost):
        self.to = to        # endpoint
        self.rev = rev      # index of reverse edge in g[to]
        self.cap = cap      # residual capacity
        self.cost = cost    # cost per unit flow

class MinCostCirculation:
    """
    Finds a minimum-cost circulation in a directed graph with capacities and costs.
    Works with negative cycles by repeatedly canceling them (Bellman-Ford).
    Graph size here is small enough for this approach.
    """
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]

    def add_edge(self, fr, to, cap, cost):
        """
        Add edge fr->to and reverse edge to->fr.
        Returns (fr, index) to identify the forward edge later.
        """
        fwd = Edge(to, len(self.g[to]), cap, cost)
        rev = Edge(fr, len(self.g[fr]), 0, -cost)
        self.g[fr].append(fwd)
        self.g[to].append(rev)
        return fr, len(self.g[fr]) - 1

    def min_cost_circulation(self):
        """
        Cycle-canceling:
        - While there exists a negative cycle in the residual graph,
          send as much flow as possible around it.
        Returns total min cost.
        """
        n = self.n
        cost_total = 0

        while True:
            # Bellman-Ford to detect any negative cycle reachable from a super source.
            # We simulate super source by initializing dist=0 for all nodes.
            dist = [0] * n
            parent_v = [-1] * n      # parent vertex in relaxation
            parent_e = [-1] * n      # parent edge index in g[parent_v]

            x = -1
            for _ in range(n):
                x = -1
                for v in range(n):
                    dv = dist[v]
                    for ei, e in enumerate(self.g[v]):
                        if e.cap <= 0:
                            continue
                        nd = dv + e.cost
                        if nd < dist[e.to]:
                            dist[e.to] = nd
                            parent_v[e.to] = v
                            parent_e[e.to] = ei
                            x = e.to

            if x == -1:
                # No relaxation on nth iteration => no negative cycle
                break

            # 'x' is on or reaches a negative cycle; move x inside the cycle
            for _ in range(n):
                x = parent_v[x]

            # Reconstruct the cycle by walking parents until we return to x
            cycle = []
            cur = x
            while True:
                pv = parent_v[cur]
                pe = parent_e[cur]
                cycle.append((pv, pe))  # edge pv -> cur is pe in g[pv]
                cur = pv
                if cur == x:
                    break

            # Determine bottleneck capacity along the cycle
            add = 10**18
            for v, ei in cycle:
                e = self.g[v][ei]
                if e.cap < add:
                    add = e.cap

            # Augment flow along the cycle and update total cost
            for v, ei in cycle:
                e = self.g[v][ei]
                rev = self.g[e.to][e.rev]
                e.cap -= add
                rev.cap += add
                cost_total += add * e.cost

        return cost_total

# -------------- Problem Solution --------------

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m1 = int(next(it))
    m2 = int(next(it))

    # G[u][v] bitmask: 1 for Juan, 2 for Rosa
    G = [[0] * n for _ in range(n)]
    for _ in range(m1):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        G[u][v] |= 1
        G[v][u] |= 1
    for _ in range(m2):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        G[u][v] |= 2
        G[v][u] |= 2

    # Bipartite coloring using all edges that exist in either set
    color = [-1] * n
    sys.setrecursionlimit(10000)

    def dfs(u, c):
        color[u] = c
        for v in range(n):
            if G[u][v] == 0:
                continue
            if color[v] == -1:
                if not dfs(v, 1 - c):
                    return False
            elif color[v] == color[u]:
                return False
        return True

    for i in range(n):
        if color[i] == -1:
            ok = dfs(i, 0)
            if not ok:
                raise RuntimeError("Graph is not bipartite")

    # Build circulation graph on 2*n nodes:
    # node u = "in", node u+n = "out"
    N = 2 * n
    mcc = MinCostCirculation(N)

    # For reconstruction, store (fr, idx, u, v, typ)
    edge_info = []

    for u in range(n):
        # capacity 1 through each vertex
        mcc.add_edge(u, u + n, 1, 0)

    for i in range(n):
        for j in range(i + 1, n):
            if G[i][j] == 0:
                continue

            # Juan edge: A(0) -> B(1)
            if G[i][j] & 1:
                if color[i] == 0 and color[j] == 1:
                    fr, idx = mcc.add_edge(i + n, j, 1, -1)
                    edge_info.append((fr, idx, i, j, 1))
                else:
                    fr, idx = mcc.add_edge(j + n, i, 1, -1)
                    edge_info.append((fr, idx, i, j, 1))

            # Rosa edge: B(1) -> A(0)
            if G[i][j] & 2:
                if color[i] == 1 and color[j] == 0:
                    fr, idx = mcc.add_edge(i + n, j, 1, -1)
                    edge_info.append((fr, idx, i, j, 2))
                else:
                    fr, idx = mcc.add_edge(j + n, i, 1, -1)
                    edge_info.append((fr, idx, i, j, 2))

    min_cost = mcc.min_cost_circulation()
    k = (-min_cost) // 2  # each marriage corresponds to 2 selected edges

    juan = []
    rosa = []

    # An original edge is chosen if its residual cap is 0 (since initial cap was 1)
    for fr, idx, u, v, typ in edge_info:
        e = mcc.g[fr][idx]
        used = (e.cap == 0)
        if used:
            if typ == 1:
                juan.append((u, v))
            else:
                rosa.append((u, v))

    out = []
    out.append(str(k))
    for u, v in juan:
        out.append(f"{u+1} {v+1}")
    for u, v in rosa:
        out.append(f"{u+1} {v+1}")
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()
```

---

## 5) Compressed editorial

Color `E1 ∪ E2` to get bipartition `A/B`. Direct Juan edges `A→B`, Rosa edges `B→A`. A subset of actors is jointly perfectly-matchable in both iff we can cover them with vertex-disjoint directed cycles alternating Juan/Rosa edges. Enforce vertex-disjointness with node-splitting (capacity-1 edge `u_in → u_out`). Give each relationship edge capacity 1 and cost -1. A minimum-cost circulation then picks as many relationship edges as possible along negative cycles. Total cost = -2k, so k = (-cost)/2. Implemented with network simplex to handle negative cycles correctly.
