## 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.
