## 1) Concise 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 (solution explanation)

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) Provided C++ solution with detailed line-by-line comments

```cpp
#include <bits/stdc++.h>              // Includes almost all standard C++ headers
using namespace std;

// Helper to print a pair as "first second"
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

// Helper to read a pair from input
template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

// Helper to read a vector: reads all elements in order
template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {                 // Iterate by reference to fill
        in >> x;
    }
    return in;
};

// Helper to print a vector (space-separated)
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {                  // Iterate by value for printing
        out << x << ' ';
    }
    return out;
};

int n;                                // Number of men and women

// Store names by id
vector<string> man_name, woman_name;

// Map names to ids for O(1)-ish lookup
map<string, int> man_id, woman_id;

// Preferences as integer ids:
// man_pref[m][k] = woman id of m's k-th choice
// woman_pref[w][k] = man id of w's k-th choice
vector<vector<int>> man_pref, woman_pref;

// Preferences temporarily stored as strings during input
vector<vector<string>> man_pref_str, woman_pref_str;

void read() {
    cin >> n;                         // Read N

    // Resize storage arrays based on 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));

    // Read men preference lists
    for(int i = 0; i < n; i++) {
        cin >> man_name[i];           // Man name
        man_id[man_name[i]] = i;      // Assign id
        for(int j = 0; j < n; j++) {
            cin >> man_pref_str[i][j]; // Store preferred woman name at position j
        }
    }

    // Read women preference lists
    for(int i = 0; i < n; i++) {
        cin >> woman_name[i];         // Woman name
        woman_id[woman_name[i]] = i;  // Assign id
        for(int j = 0; j < n; j++) {
            cin >> woman_pref_str[i][j]; // Store preferred man name at position j
        }
    }
}

void solve() {
    // Convert preferences from names to integer ids
    man_pref.resize(n, vector<int>(n));
    woman_pref.resize(n, vector<int>(n));

    // man_pref[m][j] = id of the j-th woman in man's list
    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]];
        }
    }

    // woman_pref[w][j] = id of the j-th man in woman's list
    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]];
        }
    }

    // Build ranking for women:
    // woman_rank[w][m] = position of man m in woman w's preference list
    // This lets us compare two men in O(1).
    vector<vector<int>> woman_rank(n, vector<int>(n));
    for(int i = 0; i < n; i++) {          // For each woman i
        for(int j = 0; j < n; j++) {      // For each position j
            woman_rank[i][woman_pref[i][j]] = j;
        }
    }

    // Current matches; -1 means unmatched/free
    vector<int> man_match(n, -1), woman_match(n, -1);

    // man_next[m] = next index in man_pref[m] to propose to
    vector<int> man_next(n, 0);

    // Queue of currently free men who still need to propose
    queue<int> free_men;
    for(int i = 0; i < n; i++) {
        free_men.push(i);                 // Initially everyone is free
    }

    // Gale–Shapley: while there is a free man who still can propose
    while(!free_men.empty()) {
        int m = free_men.front();         // Take a free man
        free_men.pop();

        // He proposes to his next preferred woman
        int w = man_pref[m][man_next[m]++];

        if(woman_match[w] == -1) {
            // Woman is free: engage them
            man_match[m] = w;
            woman_match[w] = m;
        } else {
            // Woman is currently engaged: decide whether she prefers new proposer
            int curr = woman_match[w];    // Current fiancé of w

            // If w prefers m (smaller rank) over curr, she switches
            if(woman_rank[w][m] < woman_rank[w][curr]) {
                man_match[m] = w;
                woman_match[w] = m;

                // Current fiancé becomes free again
                man_match[curr] = -1;
                free_men.push(curr);
            } else {
                // w rejects m; m remains free and will propose again later
                free_men.push(m);
            }
        }
    }

    // In this complete preference setting, stable matching always exists
    cout << "YES\n";

    // Output pairs (man name, matched woman name)
    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); // Speed up i/o
    cin.tie(nullptr);                 // Untie cin from cout for speed

    int T = 1;                        // Single test case in this problem
    // cin >> T;                      // (Not used)
    for(int test = 1; test <= T; test++) {
        read();                       // Read input
        // cout << "Case #" << test << ": ";
        solve();                      // Compute and print stable matching
    }

    return 0;
}
```

---

## 4) Python solution (same approach) with detailed comments

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