text: #pragma once
  #include <bits/stdc++.h>
  using namespace std;
  
  // Given N people of type A and M people of type B, and a list of their ranked
  //   preferences for partners, the goal is to arrange min(N, M) pairs such that
  //   if a person x of type A prefers a person y of type B more than their
  //   current partner, then person y prefers their current partner more than x
  // It is guaranteed that a solution always exists
  // Constructor Arguments:
  //   aPrefs: a matrix of size N x M with aPrefs[i][j] representing the jth
  //     preferred choice for the partner of type B for person i of type A;
  //     aPrefs[i] must be a permutation from 0 to M - 1
  //   bPrefs: a matrix of size M x N with bPrefs[j][i] representing the ith
  //     preferred choice for the partner of type A for person j of type B;
  //     bPrefs[j] must be a permutation from 0 to N - 1
  // Fields:
  //   N: the number of people of type A
  //   M: the number of people of type B
  //   bForA: a vector representing the partner of type B for each person of
  //     type A, or -1 if that person of type A is unmatched
  //   aForB: a vector representing the partner of type A for each person of
  //     type B, or -1 if that person of type B is unmatched
  // In practice, has a moderate constant
  // Time Complexity:
  //   constructor O(NM)
  // Memory Complexity: O(NM)
  // Tested:
  //   https://www.spoj.com/problems/STABLEMP/
  //   https://open.kattis.com/problems/jealousyoungsters
  struct StableMarriage {
    int N, M; vector<int> bForA, aForB;
    StableMarriage(const vector<vector<int>> &aPrefs,
                   const vector<vector<int>> &bPrefs)
        : N(aPrefs.size()), M(bPrefs.size()), bForA(N, -1), aForB(M, -1) {
      bool rev = N > M; if (rev) { swap(N, M); bForA.swap(aForB); }
      auto &A = rev ? bPrefs : aPrefs, &B = rev ? aPrefs : bPrefs;
      vector<vector<int>> bRankOfA(M, vector<int>(N));
      for (int b = 0; b < M; b++) for (int a = 0; a < N; a++)
        bRankOfA[b][B[b][a]] = a;
      queue<int> q; for (int a = 0; a < N; a++) q.push(a);
      vector<int> cur(N, 0); while (!q.empty()) {
        int a = q.front(); q.pop(); while (true) {
          int b = A[a][cur[a]++]; if (aForB[b] == -1) { aForB[b] = a; break; }
          else if (bRankOfA[b][a] < bRankOfA[b][aForB[b]]) {
            q.push(aForB[b]); aForB[b] = a; break;
          }
        }
      }
      for (int b = 0; b < M; b++) if (aForB[b] != -1) bForA[aForB[b]] = b;
      if (rev) { swap(N, M); bForA.swap(aForB); }
    }
  };
  