#include <bits/stdc++.h>
#include "library.h"
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 2e5+10;
const int SQRT = 610;
const int MAXA = 50;
const int MOD = 998244353;
const int INF = 1e9+10;
const int LOG = 21;
const ld EPS = 1e-12;
vector <int> que, adj[1010], ans;
vector <pii> edge;
int n;
struct dsu {
int par[MAXN];
void bd(){
for(int i=0; i<n; i++) par[i] = i;
}
int f(int x){
return (par[x]==x ? x : par[x]=f(par[x]));
}
void mer(int x, int y){
x = f(x); y = f(y);
if(x==y) return;
par[x] = y;
}
} DSU;
void dfs(int nw, int par){
ans.pb(nw+1);
for(auto nx : adj[nw]){
if(nx==par) continue;
dfs(nx, nw);
}
}
void RESET(){
for(int i=0;i<n;i++) que[i] = 0;
}
void RANGE(int x, int y){
for(int i=0; i<n; i++){
if(DSU.f(i)==x || DSU.f(i)==y) que[i] = 1;
}
}
void Solve(int N)
{
n = N;
que.resize(n); DSU.bd();
edge.pb({0,0});
for(int i=1; i<n; i++){
int l=0, r=edge.size()-1, mid=0, cnt=-1;
while(l<=r){
mid = md;
RESET(); que[i] = 1;
for(int i=0; i<=mid; i++)
RANGE(edge[i].fi, edge[i].se);
if(Query(que) == mid+2) cnt = mid, l = mid+1;
else r = mid-1;
}
// cout << i<<" i\n";
// for(auto [x,y]:edge) cout << x << ' '<<y << "xy\n";
if(cnt == edge.size()-1){
edge.pb({i,i}); continue;
}
// cnt+1, merge 1 side
RESET(); que[i] = 1; que[edge[cnt+1].fi] = 1;
int le = -1, ri = -1;
if(Query(que) == 1) le = edge[cnt+1].fi;
else le = edge[cnt+1].se;
if(edge.size()-1 < cnt+2){
vector <pii> vec;
DSU.mer(i, le);
adj[i].pb(le); adj[le].pb(i);
// cout <<le << ' '<< i << "lei\n";
for(auto [x,y] : edge){
if(x==le) vec.pb({i, y});
else if(y==le) vec.pb({i, x});
else vec.pb({x,y});
}
swap(vec, edge);
continue;
}
l = cnt+2, r=edge.size()-1, mid=0; int cnt2 = cnt+1;
while(l<=r){
mid = md;
RESET(); que[i] = 1;
for(int i=cnt+2; i<=mid; i++)
RANGE(edge[i].fi, edge[i].se);
if(Query(que) == mid-cnt-1 + 1) cnt2 = mid, l = mid+1;
else r = mid-1;
}
if(cnt2 < edge.size()-1){ // cnt2+1, merge ri
RESET(); que[i] = 1; que[edge[cnt2+1].fi] = 1;
if(Query(que) == 1) ri = edge[cnt2+1].fi;
else ri = edge[cnt2+1].se;
} else {
vector <pii> vec;
DSU.mer(i, le);
adj[i].pb(le); adj[le].pb(i);
// cout <<le << ' '<< i << "lei\n";
for(auto [x,y] : edge){
if(x==le) vec.pb({i, y});
else if(y==le) vec.pb({i, x});
else vec.pb({x,y});
}
swap(vec, edge);
continue;
}
DSU.mer(i, le); DSU.mer(i, ri);
adj[i].pb(le); adj[le].pb(i);
adj[i].pb(ri); adj[ri].pb(i);
// cout << le << ' '<< i << ' '<< ri << " leri\n";
vector <pii> vec; int pp = -1;
for(auto [x,y] : edge){
if(x==le || x==ri){
if(pp==-1) pp = y;
else vec.pb({pp, y});
} else if(y==le || y==ri){
if(pp==-1) pp = x;
else vec.pb({pp, x});
} else vec.pb({x,y});
}
swap(vec, edge);
}
int sta = 0;
for(int i=0; i<n; i++)
if(adj[i].size() == 1) sta = i;
dfs(sta, -1);
Answer(ans);
}
