#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef vector vi; typedef vector vvi; typedef pair pi; #define all(x) begin(x),end(x) #define rep(i,a,b) for(int i=a;i> n; vvi adj(n); for(int i=0;i> u >> v; --u,--v; adj[u].push_back(v); adj[v].push_back(u); } vi sz(n,1); auto dfs = [&](auto&& self, int at, int from) -> void { for(int to : adj[at]) if(to!=from) { self(self,to,at); sz[at]+=sz[to]; } }; dfs(dfs,0,-1); int centr=-1; int at=0,from=-1; while(true) { bool found=0; for(int to : adj[at]) if(to!=from) { if(sz[to]*2>=n) { from=at; at=to; found=1; break; } } if(!found) { centr=at; break; } } fill(all(sz),1); auto dfs2 = [&](auto&& self, int at, int from) -> void { vi s; for(int to : adj[at]) if(to!=from) { self(self,to,at); s.push_back(sz[to]); } sort(all(s)); for(auto v : s) { if(sz[at]