#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=5e5+10,mod=1e9+7,mod2=1011451423; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n; vector<int>E[maxn]; int fa[maxn]; int c0[maxn],c1[maxn],vis[maxn]; pi f[maxn],g[maxn]; int rnd1[maxn],rnd2[maxn],rnd3[maxn]; int rnd4[maxn],rnd5[maxn],rnd6[maxn]; mt19937 rng(0); const int XOR=rng(),XOR2=rng(); inline int RD(int k){ return (k^XOR)%mod; } inline int RD2(int k){ return (k^XOR2)%mod2; } void dfs(int u,int fa){ ::fa[u]=fa; f[u]=m_p(1,1),vis[u]=u<=n;c0[u]=!vis[u],c1[u]=vis[u]; for(int x:E[u])if(x!=fa){ dfs(x,u);f[u].p1=f[u].p1*1ll*RD(f[x].p1)%mod,f[u].p2=f[u].p2*1ll*RD2(f[x].p2)%mod2,c0[u]+=c0[x],c1[u]+=c1[x]; } f[u].p1=f[u].p1*1ll*rnd1[c0[u]]%mod*1ll*rnd2[c1[u]]%mod*1ll*rnd3[c0[u]+c1[u]]%mod; f[u].p2=f[u].p2*1ll*rnd4[c0[u]]%mod2*1ll*rnd5[c1[u]]%mod2*1ll*rnd6[c0[u]+c1[u]]%mod2; } int mul1[maxn],mul2[maxn]; int mul3[maxn],mul4[maxn]; void dfs2(int u,int fa){ vector<int>son; for(int x:E[u])if(x!=fa)son.p_b(x); up(i,0,(int)son.size()-1)mul1[i]=(i?mul1[i-1]:1)*1ll*RD(f[son[i]].p1)%mod; up(i,0,(int)son.size()-1)mul3[i]=(i?mul3[i-1]:1)*1ll*RD2(f[son[i]].p2)%mod2; down(i,(int)son.size()-1,0)mul2[i]=(i+1<son.size()?mul2[i+1]:1)*1ll*RD(f[son[i]].p1)%mod; down(i,(int)son.size()-1,0)mul4[i]=(i+1<son.size()?mul4[i+1]:1)*1ll*RD2(f[son[i]].p2)%mod2; up(i,0,(int)son.size()-1){ int x=son[i]; auto t=u==1?g[u]:m_p(RD(g[u].p1),RD2(g[u].p2)); t.p1=t.p1*1ll*(i?mul1[i-1]:1)%mod*1ll*((i+1<son.size())?mul2[i+1]:1)%mod; t.p2=t.p2*1ll*(i?mul3[i-1]:1)%mod2*1ll*((i+1<son.size())?mul4[i+1]:1)%mod2; int w0=c0[1]-c0[x],w1=c1[1]-c1[x]; t.p1=t.p1*1ll*rnd1[w0]%mod*1ll*rnd2[w1]%mod*1ll*rnd3[w0+w1]%mod; t.p2=t.p2*1ll*rnd4[w0]%mod2*1ll*rnd5[w1]%mod2*1ll*rnd6[w0+w1]%mod2; g[x]=t; }for(int x:son)dfs2(x,u); } void slv(){ n=read(); up(i,1,n-1){ int x=read(),y=read(); E[x].p_b(y),E[y].p_b(x); } int tot=n; up(i,1,n)while(E[i].size()<4)++tot,E[i].p_b(tot),E[tot].p_b(i); auto rnd=[](int mod){auto k=rng();while(k%mod==0)k=rng();return k%mod;}; up(i,0,tot)rnd1[i]=rnd(mod),rnd2[i]=rnd(mod),rnd3[i]=rnd(mod),rnd4[i]=rnd(mod2),rnd5[i]=rnd(mod2),rnd6[i]=rnd(mod2); dfs(1,0),g[1]=m_p(1,1);dfs2(1,0); set<pair<pi,pi> >A,B; up(i,1,n)for(int x:E[i])if(i<x){ if(vis[x]){ if(fa[x]==i)B.insert(m_p(f[x],g[x])),B.insert(m_p(g[x],f[x])); else B.insert(m_p(f[i],g[i])),B.insert(m_p(g[i],f[i])); }else { A.insert(m_p(f[x],g[x])); B.insert(m_p(g[x],f[x])); } } printf("%lu %lu\n",A.size(),B.size()); } int main(){ //freopen("isomer.in","r",stdin),freopen("isomer.out","w",stdout); slv(); return 0; }