#include"wheretoreach.h"
#include"implementer.cpp"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1e5+3;
int tot,d[N];
void Sol(vector<int> &a)
{
	int n=(int)a.size();assert(n>1);
	if(n==2){report(a[0],a[1]);tot++;return;}
	int rt=0,rtsz=n;
	for(int x:a)
	{
		d[x]=remove(x),add(x);
		if(d[x]<rtsz)rtsz=d[x],rt=x;
	}
	vector<array<int,2>>b;
	for(int x:a)if(x!=rt)b.pb({n-d[x],x});
	sort(b.begin(),b.end());
	vector<int>QA,QB;QA.pb(rt);QB.pb(rt);
	int mx=n,val=n,fl=0;
	for(auto [v,id]:b)
	{
		int tmp=remove(id);
    	if(fl)
		{
      		if(tmp<mx)add(id),QB.pb(id);
      		else QA.pb(id);
    	}
		else
		{
      		int del=max(n-tmp+1,tmp);
      		if(del<=val)QA.pb(id),mx=tmp,val=del;
      		else fl=1,add(id),QB.pb(id);
    	}
	}
	Sol(QB);
	if(QA.size()>2)
	{
		for(int i=0;i+1<(int)QB.size();i++)if(QB[i]!=rt)remove(QB[i]);
		for(int id:QA)if(id!=rt)add(id);
	}
	Sol(QA);
}
void solve(int n)
{
	vector<int>a;
	for(int i=1;i<=n;i++)add(i),a.pb(i);
	Sol(a);
}

implementer.cpp: In function ‘void Interactor::init()’:
implementer.cpp:25:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   25 |                 scanf("%d",&n);
      |                 ~~~~~^~~~~~~~~
implementer.cpp:30:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   30 |                         scanf("%d%d",&x,&y); v[x].push_back(y),v[y].push_back(x);
      |                         ~~~~~^~~~~~~~~~~~~~
In file included from answer.code:2:
implementer.cpp: In function ‘void Interactor::init()’:
implementer.cpp:25:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   25 |                 scanf("%d",&n);
      |                 ~~~~~^~~~~~~~~
implementer.cpp:30:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   30 |                         scanf("%d%d",&x,&y); v[x].push_back(y),v[y].push_back(x);
      |                         ~~~~~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x6b720): multiple definition of `Interactor::v'; /tmp/cc4His6J.o:(.bss+0x9c80): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o: in function `Interactor::dfs1(int, int)':
answer.code:(.text+0x8d0): multiple definition of `Interactor::dfs1(int, int)'; /tmp/cc4His6J.o:implementer.cpp:(.text+0x4b0): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x1c1a60): multiple definition of `Interactor::f'; /tmp/cc4His6J.o:(.bss+0x15ffc0): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x19a860): multiple definition of `Interactor::dep'; /tmp/cc4His6J.o:(.bss+0x138dc0): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x190be0): multiple definition of `Interactor::siz'; /tmp/cc4His6J.o:(.bss+0x12f140): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x186f60): multiple definition of `Interactor::wsn'; /tmp/cc4His6J.o:(.bss+0x1254c0): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o: in function `Interactor::dfs2(int, int, int)':
answer.code:(.text+0x990): multiple definition of `Interactor::dfs2(int, int, int)'; /tmp/cc4His6J.o:implementer.cpp:(.text+0x570): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x17d2e0): multiple definition of `Interactor::tp'; /tmp/cc4His6J.o:(.bss+0x11b840): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x1ae160): multiple definition of `Interactor::ed'; /tmp/cc4His6J.o:(.bss+0x14c6c0): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x1b7de0): multiple definition of `Interactor::dfn'; /tmp/cc4His6J.o:(.bss+0x156340): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x1cb6cc): multiple definition of `Interactor::tot'; /tmp/cc4His6J.o:(.bss+0x169c2c): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x1a44e0): multiple definition of `Interactor::rev'; /tmp/cc4His6J.o:(.bss+0x142a40): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x173660): multiple definition of `Interactor::bt'; /tmp/cc4His6J.o:(.bss+0x111bc0): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x1699e0): multiple definition of `Interactor::bla'; /tmp/cc4His6J.o:(.bss+0x107f40): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o: in function `Interactor::init()':
answer.code:(.text+0xaa0): multiple definition of `Interactor::init()'; /tmp/cc4His6J.o:implementer.cpp:(.text+0x680): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x1cb6d8): multiple definition of `Interactor::n'; /tmp/cc4His6J.o:(.bss+0x169c38): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x1cb6c8): multiple definition of `Interactor::tid'; /tmp/cc4His6J.o:(.bss+0x169c28): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0xb9a80): multiple definition of `Interactor::iedge'; /tmp/cc4His6J.o:(.bss+0x57fe0): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x1cb6d0): multiple definition of `Interactor::y'; /tmp/cc4His6J.o:(.bss+0x169c30): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x1cb6d4): multiple definition of `Interactor::x'; /tmp/cc4His6J.o:(.bss+0x169c34): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o: in function `Interactor::sprdv(int, int)':
answer.code:(.text+0xf40): multiple definition of `Interactor::sprdv(int, int)'; /tmp/cc4His6J.o:implementer.cpp:(.text+0xb20): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x142840): multiple definition of `Interactor::val'; /tmp/cc4His6J.o:(.bss+0xe0da0): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o:(.bss+0x11b6a0): multiple definition of `Interactor::tval'; /tmp/cc4His6J.o:(.bss+0xb9c00): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o: in function `Interactor::modifyv(int, int, int, int, int, int)':
answer.code:(.text+0xf60): multiple definition of `Interactor::modifyv(int, int, int, int, int, int)'; /tmp/cc4His6J.o:implementer.cpp:(.text+0xb40): first defined here
/usr/bin/ld: /tmp/ccPgCtdN.o: in f...