#include #define fr(i,n) for(int i=0;i<(n);++i) #define foor(i,a,b) for(int i=(a);i<=(b);++i) #define rf(i,n) for(int i=(n);i--;) #define roof(i,b,a) for(int i=(b);i>=(a);--i) #define elsif else if #define all(x) x.begin(),x.end() #define Sort(x) sort(all(x)) #define Reverse(x) reverse(all(x)) #define PQ priority_queue #define NP(x) next_permutation(all(x)) #define M_PI 3.14159265358979323846 using namespace std; typedef vector vb; typedef vector vvb; typedef vector vi; typedef vector vvi; typedef long long ll; typedef vector< ll> vl; typedef vector vvl; typedef unsigned long long ull; typedef vector vu; typedef vector vvu; typedef double dbl; typedef vector vd; typedef vector vvd; typedef string str; typedef vector vs; typedef vector vvs; typedef pairpii; typedef vectorvpii; typedef mapmii; typedef pair< ll, ll>pll; typedef vectorvpll; typedef map< ll, ll>mll; typedef pairpdd; typedef vectorvpdd; typedef mapmdd; typedef pairpss; typedef vectorvpss; typedef mapmss; typedef pairpil; typedef vectorvpil; typedef mapmil; typedef pair< ll,int>pli; typedef vectorvpli; typedef map< ll,int>mli; typedef pairpdi; typedef vectorvpdi; typedef mapmdi; templatevector&operator<<(vector&v,const T t){v.push_back(t);return v;} templatemultiset&operator<<(multiset&m,const T t){m.insert(t);return m;} templateset&operator<<(set&s,const T t){s.insert(t);return s;} templatestack&operator<<(stack&s,const T t){s.push(t);return s;} templatequeue&operator<<(queue&q,const T t){q.push(t);return q;} templatePQ,U>&operator<<(PQ,U>&q,const T t){q.push(t);return q;} templateistream&operator>>(istream&s,pair&p){return s>>p.first>>p.second;} templateistream&operator>>(istream&s,vector&v){fr(i,v.size()){s>>v[i];}return s;} templateostream&operator<<(ostream&s,const pairp){return s<ostream&operator<<(ostream&s,const vectorv){for(auto a:v){s<ostream&operator<<(ostream&s,const vectorv){fr(i,v.size()){i?s<<" "<pairoperator+(paira,pairb){return {a.first+b.first,a.second+b.second};} templatepairoperator-(paira,pairb){return {a.first-b.first,a.second-b.second};} void print(void){cout<void print(T t){cout<void print(T&&t,U&&...u){cout<(u)...);} void YN(bool b){print(b?"YES":"NO");}void PI(bool b){print(b?"POSSIBLE":"IMPOSSIBLE");} void Yn(bool b){print(b?"Yes":"No");}void Pi(bool b){print(b?"Possible":"Impossible");} void yn(bool b){print(b?"yes":"no");}void pi(bool b){print(b?"possible":"impossible");} const int MD=1e9+7; templatestr to_string(const T&n){ostringstream s;s<vector>dijkstra(const vector>>E,const U s,const T inf){using P=pair;vector

d;fr(i,E.size()){d<,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstmap>dijkstra(map>>E,const U s,const T inf){using P=pair;mapd;for(pair>e:E){d[e.first]=P{inf,e.first};}PQ,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstT distsq(paira,pairb){return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);} templateT max(const vectora){T m=a[0];for(T e:a){m=max(m,e);}return m;} templateT min(const vectora){T m=a[0];for(T e:a){m=min(m,e);}return m;} templateT gcd(const T a,const T b){return a?gcd(b%a,a):b;} templateT gcd(const vectora){T g=a[0];for(T e:a){g=gcd(g,e);}return g;} templatevectorLIS(const vectorA){vi B;for(T a:A){auto it=lower_bound(all(B),a);if(it==B.end()){B<vector>ConvexHull(vector>V){if(V.size()<=3){return V;}Sort(V);rf(i,V.size()-1)V<>r;for(pairp:V){int s=r.size();while(s>=2&&(p.second-r[s-1].second)*(p.first-r[s-2].first)<(p.second-r[s-2].second)*(p.first-r[s-1].first)){r.pop_back();--s;}r<r[b=find(b)]){swap(a,b);}s[b]+=s[a];r[p[a]=b]+=r[a]==r[b];}bool same(int a,int b){return find(a)==find(b);}int size(int x){return s[find(x)];}}; ll strmod(const str&s,const int m){ll x=0;fr(i,s.size()){x=(x*10+s[i]-48)%m;}return x;} vvl mul(const vvl&A,const vvl&B,const int m){vvl C;fr(y,A.size()){C<=0?a%m:(m-(-a%m))%m:1)*(t=pow(a,n>>1,m),t*t%m)%m:!!a;} ll inv(const ll x,const int p){return pow(x,p-2,p);} vpll fact(const int n,const int p){vpll v(n+1);v[0].first=1;foor(i,1,n){v[i].first=v[i-1].first*i%p;}v[n].second=inv(v[n].first,p);roof(i,n,1){v[i-1].second=v[i].second*i%p;}return v;} class Combination{const vpll f;const int M;public:Combination(int n,int m):f(fact(n,m)),M(m){}Combination(int n):Combination(n,MD){}ll P(int n,int k){return n<0||k<0||n>1;r|=s.size()>>1;if(l>r){return 0;}if(l==r){return s[l];}ll z=s[l]+s[r];for(;l>>1>1;l>>=1,r>>=1){l&1||(z+=s[l^1]);r&1&&(z+=s[r^1]);}return z;} void segadd(vl&s,int i,ll x){s[i|=s.size()>>1]+=x;for(;i>>1>=1;i>>=1){s[i>>1]=s[i]+s[i^1];}} ll BITsum(vl&B,int i){ll z=0;while(i>0){z+=B[i];i-=i&-i;}return z;} void BITadd(vl&B,int i,ll x){while(i>i&1){a=A;b=B;c=C;d=D;A=a+b;B=a;C=c+d;D=c;}a=A%m;b=B%m;c=C%m;d=D%m;}return b;} vi primes(int n){vb b(n+1);vi p;foor(i,2,n){if(!b[i]){p<>N; if(N==1){ print(1); return 0; } vvi E(N); fr(i,N-1){ int a,b;cin>>a>>b; --a;--b; E[a]<