#include <bits/stdc++.h>
using namespace std;
#include "evolution2.h"
const int N = 1e5 + 10;
int p[N], pp[N], cur, pos[N], h[N], c, tmp[N], ct, pl[N], l2[N];
vector<int>g[N];

void mg(int a, int b, int C)
{
	if(a>b) return;
	int i, j, k;
	int *x = p + a - 1, n = b - a + 1, *y = p + b, m = C - b;
	if(n<m) swap(x,y), swap(n,m);
	pos[1] = 1;
	int A = (n + m - 1) / m, B = l2[A];
	if((1<<B)<A) B++;
	A = 1 << B;
	for(i=1;pos[i]+A<=n;i++) pos[i+1] = pos[i] + A;
	int cl = i;
	pos[cl+1] = n + 1;
	
	c = ct = 0;
	if(cl==1)
	{
		int u = 1;
		for(i=1;i<=m;i++)
		{
			int l = 0, r = n, mid;
			while(l<r)
			{
				mid = (l + r + 1) >> 1;
				if(compare(x[mid],y[i])) l = mid;
				else r = mid - 1;
			}
			for(;u<=l;u++) tmp[++ct] = x[u];
			tmp[++ct] = y[i];
		}
		for(;u<=n;u++) tmp[++ct] = x[u];
	}
	else
	{
		int s = 1, t = 1;
		while(s<=cl&&t<=m)
		{
			if(compare(x[pos[s]],y[t])) h[++c] = -(s++);
			else h[++c] = y[t++];
		}
		while(s<=cl) h[++c] = -(s++);
		while(t<=m) h[++c] = y[t++];
		for(i=1;i<=c&&h[i]>0;i++) tmp[++ct] = h[i];
		for(;i<=c;)
		{
			int u = pos[-h[i]];
			for(j=i+1;j<=c&&h[j]>0;j++);
			for(k=i+1;k<j;k++)
			{
				int l = pos[-h[i]], r = pos[-h[i]+1] - 1, mid;
				while(l<r)
				{
					mid = (l + r + 1) >> 1;
					if(compare(x[mid],h[k])) l = mid;
					else r = mid - 1;
				}
				for(;u<=l;u++) tmp[++ct] = x[u];
				tmp[++ct] = h[k];
			}
			for(;u<pos[-h[i]+1];u++) tmp[++ct] = x[u];
			i = j;
		}
	}
	for(i=a;i<=C;i++) p[i] = tmp[i-a+1];
}

void dfs(int x)
{
	p[++cur] = x;
	int l = cur + 1;
	for(auto j:g[x])
	{
		int m = cur;
		dfs(j);
		mg(l,m,cur);
	}
}

std::vector<int> recover(int n, std::vector<int> U, std::vector<int> V) {
	std::vector<int> res = {};
	cur = 0;
	int i;
	for(i=2;i<=n;i++) l2[i] = l2[i/2] + 1;
	for(i=0;i<n;i++) g[i].clear();
	for(i=0;i<n-1;i++) g[U[i]].emplace_back(V[i]);
	dfs(0);
	for(i=1;i<=n;i++) pp[p[i]] = i - 1;
	for(i=0;i<n;i++) res.emplace_back(pp[i]);
	return res;
}