namespace Prufer
{
int n,fa[MAX],deg[MAX],p[MAX];
inline void MakePrufer()
{
for(int i=1;i<=n-1;++i) ++deg[fa[i]];
for(int i=1,j=1;i<=n-2;++i,++j)
{
while(deg[j]) ++j;
p[i]=fa[j];
while(i<=n-2&&!--deg[p[i]]&&p[i]<j) p[i+1]=fa[p[i]],++i;
}
}
inline void TransPrufer()
{
for(int i=1;i<=n-2;++i) ++deg[p[i]];
p[n-1]=n;
for(int i=1,j=1;i<=n-1;++i,++j)
{
while(deg[j]) ++j;
fa[j]=p[i];
while(i<=n-2&&!--deg[p[i]]&&p[i]<j) fa[p[i]]=p[i+1],++i;
}
}
}