1. Abridged Problem Statement

There are N men and N women (1 ≤ N ≤ 800). Each person provides a complete preference list ranking all people of the opposite sex from best to worst.

A perfect assignment matches every man to exactly one woman and every woman to exactly one man.

A pair (m, w) not matched to each other is unstable if:
- m prefers w over his current partner, and
- w prefers m over her current partner.

Task: Output YES and any stable perfect assignment (no unstable pairs). (In this setting a stable matching always exists.)

2. Detailed Editorial

This is the classic Stable Marriage problem. Since every preference list contains all N partners, the underlying bipartite graph is complete, and a stable matching is guaranteed to exist. The standard algorithm to find one is the Gale–Shapley (deferred acceptance) algorithm.

Key idea (men propose)
- Each man proposes to women in decreasing preference order.
- Each woman keeps the best proposal she has received so far (according to her preferences) and rejects the others.
- Rejected men keep proposing to their next choice.
- This continues until everyone is matched.

This process is called “deferred acceptance” because a woman’s acceptance is tentative: she may later drop her current match if a more preferred man proposes.

Data representation
Names are strings, but we want fast O(1) comparisons and array indexing:
1. Map each man name → integer id (0..N-1)
2. Map each woman name → integer id (0..N-1)
3. Convert each preference list from names to ids:
   - man_pref[m][k] = woman id who is man m’s k-th choice
   - woman_pref[w][k] = man id who is woman w’s k-th choice

To decide which man a woman prefers between two candidates quickly, build:
- woman_rank[w][m] = position (rank) of man m in woman w’s list (smaller = more preferred)

This allows comparison in O(1).

Algorithm steps
Maintain:
- man_match[m] = woman id matched with man m, or -1 if free
- woman_match[w] = man id matched with woman w, or -1 if free
- man_next[m] = next index in man_pref[m] to propose to
- queue of free men

Process:
1. Initialize all men free, enqueue all men.
2. While queue not empty:
   - take a free man m
   - let w = man_pref[m][man_next[m]], increment man_next[m]
   - if w is free: match (m, w)
   - else w currently matched with curr
     - if w prefers m over curr (using woman_rank): match (m, w), make curr free and enqueue curr
     - else: m remains free, enqueue m again

Correctness sketch
Termination: Each proposal advances man_next[m] by 1, and each man can propose to at most N women, so there are at most N² proposals.

Perfect matching: When the algorithm stops, no man is free (queue empty), so everyone is matched.

Stability: Suppose there were an unstable pair (m, w). Then m must have proposed to w at some point (since he proposes in preference order and prefers w to his final partner). When he proposed, w either was free and would have accepted, or she rejected him in favor of someone she prefers more. From then on, w’s partner can only improve (she only “trades up”). Thus w cannot end up preferring m over her final partner—contradiction. So the produced matching is stable.

Complexity
- Building ranks: O(N²)
- Proposals: O(N²)
- Total: O(N²) time, O(N²) memory (fits for N ≤ 800)

3. C++ Solution

```cpp
#include <bits/stdc++.h>

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;
};

int n;
vector<string> man_name, woman_name;
map<string, int> man_id, woman_id;
vector<vector<int>> man_pref, woman_pref;

vector<vector<string>> man_pref_str, woman_pref_str;

void read() {
    cin >> n;
    man_name.resize(n);
    woman_name.resize(n);
    man_pref_str.resize(n, vector<string>(n));
    woman_pref_str.resize(n, vector<string>(n));

    for(int i = 0; i < n; i++) {
        cin >> man_name[i];
        man_id[man_name[i]] = i;
        for(int j = 0; j < n; j++) {
            cin >> man_pref_str[i][j];
        }
    }
    for(int i = 0; i < n; i++) {
        cin >> woman_name[i];
        woman_id[woman_name[i]] = i;
        for(int j = 0; j < n; j++) {
            cin >> woman_pref_str[i][j];
        }
    }
}

void solve() {
    // We should first start with some observations like the graph being
    // complete. This means that any permutation of length N corresponds to a
    // valid marriage, and the "hard" part of the problem is to find one that
    // is stable. Here we will present a very simple quadratic approach that
    // always guarantees this can be done.
    //
    // Let's incrementally add preferences, and try matching everyone who still
    // hasn't had a match. More precisely, in the first round we will match all
    // men to their top preference. This might give a case where more than one
    // man is matched to a women, so let's only keep the top match. Then we will
    // proceed to the next round that will only consider the unmatched men. It's
    // easy to implement this in O(N^2), and we can show that it will always
    // find a stable matching after N rounds. It's enough to show this via the
    // following two:
    //
    //     1) After N rounds, everyone will be matched. This is direct from the
    //        fact that at least one unmatched man/woman gets matched in a
    //        round.
    //
    //     2) We always keep the invariant that the subset of people already
    //        matched is stable. Particularly, we incrementally add preferences
    //        so on round K, all matches so far have a preference on position
    //        less than K in their preference list. This means that none of the
    //        pairs including the new people being matched at round K will break
    //        the stability and so the invariant is kept.
    //
    // A nice way of implementing this is to somewhat break the concept of
    // rounds and instead always keep a queue of unmatched people. Then each
    // operation will either match to someone unmatched, or replace the existing
    // match (which can only happen within the same round). As already
    // mentioned, this quadratic algorithm always finds a valid stable marriage.
    // It turns out that this is a popular algorithm in literature. It was
    // introduced in 1962 by Gale and Shapley, but later on in 1984 Alvin E.
    // Roth pointed out this approach had been used since the 1950 for matching
    // medical students with residency. Shapley and Roth then jointly won the
    // Nobel prize in Economics in 2012.
    //
    // https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm

    man_pref.resize(n, vector<int>(n));
    woman_pref.resize(n, vector<int>(n));

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            man_pref[i][j] = woman_id[man_pref_str[i][j]];
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            woman_pref[i][j] = man_id[woman_pref_str[i][j]];
        }
    }

    vector<vector<int>> woman_rank(n, vector<int>(n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            woman_rank[i][woman_pref[i][j]] = j;
        }
    }

    vector<int> man_match(n, -1), woman_match(n, -1);
    vector<int> man_next(n, 0);

    queue<int> free_men;
    for(int i = 0; i < n; i++) {
        free_men.push(i);
    }

    while(!free_men.empty()) {
        int m = free_men.front();
        free_men.pop();

        int w = man_pref[m][man_next[m]++];
        if(woman_match[w] == -1) {
            man_match[m] = w;
            woman_match[w] = m;
        } else {
            int curr = woman_match[w];
            if(woman_rank[w][m] < woman_rank[w][curr]) {
                man_match[m] = w;
                woman_match[w] = m;
                man_match[curr] = -1;
                free_men.push(curr);
            } else {
                free_men.push(m);
            }
        }
    }

    cout << "YES\n";
    for(int i = 0; i < n; i++) {
        cout << man_name[i] << " " << woman_name[man_match[i]] << "\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

```python
import sys
from collections import deque

def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    n = int(next(it))  # number of men and women

    # Read men block: each line is
    # <man> <woman1> <woman2> ... <womanN>
    men_names = [None] * n
    men_pref_names = [[None] * n for _ in range(n)]
    man_id = {}

    for i in range(n):
        name = next(it).decode()
        men_names[i] = name
        man_id[name] = i
        for j in range(n):
            men_pref_names[i][j] = next(it).decode()

    # Read women block: each line is
    # <woman> <man1> <man2> ... <manN>
    women_names = [None] * n
    women_pref_names = [[None] * n for _ in range(n)]
    woman_id = {}

    for i in range(n):
        name = next(it).decode()
        women_names[i] = name
        woman_id[name] = i
        for j in range(n):
            women_pref_names[i][j] = next(it).decode()

    # Convert men's preference lists from names -> woman ids
    men_pref = [[0] * n for _ in range(n)]
    for m in range(n):
        for k in range(n):
            men_pref[m][k] = woman_id[men_pref_names[m][k]]

    # Convert women's preference lists from names -> man ids
    women_pref = [[0] * n for _ in range(n)]
    for w in range(n):
        for k in range(n):
            women_pref[w][k] = man_id[women_pref_names[w][k]]

    # Build rank table for women:
    # woman_rank[w][m] = how much woman w likes man m (smaller is better)
    woman_rank = [[0] * n for _ in range(n)]
    for w in range(n):
        for pos in range(n):
            m = women_pref[w][pos]
            woman_rank[w][m] = pos

    # Matching arrays: -1 means free
    man_match = [-1] * n
    woman_match = [-1] * n

    # Next proposal index for each man
    man_next = [0] * n

    # Queue of free men
    q = deque(range(n))

    # Gale–Shapley loop
    while q:
        m = q.popleft()

        # Propose to the next woman on m's list
        w = men_pref[m][man_next[m]]
        man_next[m] += 1

        if woman_match[w] == -1:
            # Woman is free: match
            woman_match[w] = m
            man_match[m] = w
        else:
            # Woman is taken: compare current fiancé and new proposer
            curr = woman_match[w]
            if woman_rank[w][m] < woman_rank[w][curr]:
                # Woman prefers m, so she switches
                woman_match[w] = m
                man_match[m] = w

                # Old fiancé becomes free again
                man_match[curr] = -1
                q.append(curr)
            else:
                # Woman rejects m; m stays free and tries again later
                q.append(m)

    # Output (stable matching always exists here)
    out_lines = ["YES"]
    for m in range(n):
        out_lines.append(f"{men_names[m]} {women_names[man_match[m]]}")
    sys.stdout.write("\n".join(out_lines))

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

5. Compressed Editorial

Use Gale–Shapley. Map all names to ids. Convert preference lists to integer arrays. Precompute woman_rank[w][m] (position of man m in woman w’s list) for O(1) comparisons. Maintain a queue of free men; each man proposes to women in order using pointer man_next[m]. A woman accepts if free or if she prefers the new proposer over her current match; otherwise she rejects. Each man proposes at most N times ⇒ O(N²). Output “YES” and the resulting pairs; stable matching is guaranteed with complete lists.
