#include #define debug(x) cerr << #x << ": " << x << '\n' #define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector vll; const ll INF = LLONG_MAX/2; const ll MOD = 1e9+7; struct bipartiteGraph{ int L, R; vector> adj; vector mate; bipartiteGraph(int L, int R) : L(L), R(R), adj(L+R),mate(L+R, -1) { } void add_edge(int u, int v) { adj[u].push_back(v+L); adj[v+L].push_back(u); } int maximum_matching() { vector level(L); function levelize = [&]() { // BFS queue Q; for (int u = 0; u < L; ++u) { level[u] = -1; if (mate[u] < 0) { level[u] = 0; Q.push(u); } } while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int w: adj[u]) { int v = mate[w]; if (v < 0) return true; if (level[v] < 0) { level[v] = level[u] + 1; Q.push(v); } } } return false; }; function augment = [&](int u) { // DFS for (int w: adj[u]) { int v = mate[w]; if (v < 0 || (level[v] > level[u] && augment(v))) { mate[u] = w; mate[w] = u; return true; } } return false; }; int match = 0; while (levelize()) for (int u = 0; u < L; ++u) if (mate[u] < 0 && augment(u)) ++match; return match; } int lPartner(int l){ return mate[l]-L; } int rPartner(int r){ return mate[r+L]; } }; ll gcd(ll x,ll y){ return y? gcd(y,x%y):x; } signed main(){ cin.tie(0); ios::sync_with_stdio(false); ll N;cin>>N; bipartiteGraph g(N,N); for(ll i=0;i>A; for(ll j=0;j