#include "key.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
const int N = 1005;
int n, par[N], cyc[N], cs[N], cc;
pii ord[N];
bool vis[N];
vector<int> ci[N];
int dfs (int I) {
if(vis[I]) return 0;
if(cyc[I]) {
for(auto &T : ci[cyc[I]]) {
vis[T] = true;
}
return cs[cyc[I]];
}
else {
vis[I] = true;
return dfs(par[I]) + 1;
}
}
int Try (vector<int> &V) {
fill(vis+1, vis+1+n, false);
int R = 0;
for(auto &T : V) {
R += dfs(T);
}
return R;
}
void EnsureKeyInfo(int _N) {
n = _N;
for(int i=1;i<=n;i++) {
TakeKey(i);
int T = Explore();
ord[i] = {T, i};
}
sort(ord+1, ord+1+n);
for(int i=1;i<=n;i++) {
if(ord[i].X == 1) {
cyc[ord[i].Y] = ++cc;
cs[cc] = 1;
ci[cc].push_back(ord[i].Y);
continue;
}
int S = 1, E = i;
bool inc = false;
while(S<E) {
int M = (S+E)/2;
vector<int> V;
for(int j=1;j<=M;j++) {
V.push_back(ord[j].Y);
TakeKey(ord[j].Y);
}
TakeKey(ord[i].Y);
int A = Try(V), B = Explore();
if(B - A == 0) inc = true;
if(B - A <= 1) E = M;
else S = M+1;
}
if(S == i) {
cyc[ord[i].Y] = ++cc;
cs[cc] = ord[i].X;
ci[cc].push_back(ord[i].Y);
continue;
}
else if(inc) {
cyc[ord[i].Y] = cyc[ord[S].Y];
ci[cyc[ord[S].Y]].push_back(ord[i].Y);
}
else par[ord[i].Y] = ord[S].Y;
}
for(int i=1;i<=n;i++) {
fill(vis+1, vis+1+n, false);
dfs(i);
for(int j=1;j<=n;j++) {
if(vis[j]) Report(i, j);
}
}
}
