#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

namespace asdfg
{
	const int N=101000;

	int begin[N],next[N*2],to[N*2];
	int fa[N],ind[N];

	int n,m,e,S,T;

	void add(int x,int y,bool k=1)
	{
		to[++e]=y;
		next[e]=begin[x];
		begin[x]=e;
		if(k)add(y,x,0);
	}
	int bfs(int p)
	{
		static std::queue<int> Q;

		for(int i=1;i<=n;i++)ind[i]=0;
		while(!Q.empty())Q.pop();

		int ret=-1;

		for(Q.push(p);!Q.empty();)
		{
			ret=p=Q.front(),Q.pop();
			ind[p]=1;
			for(int i=begin[p],q;i;i=next[i])
				if(!ind[q=to[i]])Q.push(q);
		}
		return ret;
	}
	void dfs(int p,int h=0)
	{
		fa[p]=h;
		for(int i=begin[p],q;i;i=next[i])
			if((q=to[i])!=h)dfs(q,p);
	}
	void initialize()
	{
		scanf("%d",&n);
		for(int i=1,u,v;i<n;i++)
			scanf("%d%d",&u,&v),add(u,v);

		T=bfs(S=bfs(1)),dfs(S);

		for(int i=1;i<=n;i++)ind[i]=0;
		for(int p=T;p;p=fa[p])ind[p]=++m;
	}
	bool check(int p)
	{
		for(int i=begin[p],q;i;i=next[i])
			if(ind[q=to[i]]==0)return 0;
		return 1;
	}
	int seq[N];
	bool judge()
	{
		for(int i=1;i<=m;i++)seq[i]=1;
		for(int p=T;p;p=fa[p])
		{
			for(int i=begin[p],q;i;i=next[i])
				if(ind[q=to[i]]==0)
				{
					if(!check(q))return 0;
					seq[ind[p]]++;
				}
		}
		return 1;
	}

	int s[N],t0[N],t1[N],t[N];

	void adjust()
	{
		for(int i=1;i<=n;i++)
			if(t0[i]!=t1[i])
			{
				if(t0[i]<t1[i])memcpy(t+i,t0+i,(n-i+1)*4);
				else memcpy(t+i,t1+i,(n-i+1)*4);
				break;
			}
			else t[i]=t0[i];
	}

	void work(int *ans)
	{
		int lst=0,tmp=0;
		for(int i=1;i<=m;i++)
		{
			s[++tmp]=lst+seq[i];
			for(int j=1;j<seq[i];j++)
				s[++tmp]=lst+j;
			lst+=seq[i];
		}
		for(int i=1;i<=n;i++)
			ans[s[i]]=i;
	}
	void solve()
	{
		initialize();
		if(!judge()){printf("-1\n");return;}

		work(t0);
		std::reverse(seq+1,seq+m+1);
		work(t1);

		adjust();

		for(int i=1;i<=n;i++)
			printf("%d ",t[i]);
		printf("\n");
	}
}

int main()
{
	asdfg::solve();
	return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

Takahashi has an ability to generate a tree using a permutation (p_1,p_2,...,p_n) of (1,2,...,n), in the following process:

First, prepare Vertex 1, Vertex 2, ..., Vertex N. For each i=1,2,...,n, perform the following operation:

* If p_i = 1, do nothing.
* If p_i \neq 1, let j' be the largest j such that p_j < p_i. Span an edge between Vertex i and Vertex j'.



Takahashi is trying to make his favorite tree with this ability. His favorite tree has n vertices from Vertex 1 through Vertex n, and its i-th edge connects Vertex v_i and w_i. Determine if he can make a tree isomorphic to his favorite tree by using a proper permutation. If he can do so, find the lexicographically smallest such permutation.

Constraints

* 2 \leq n \leq 10^5
* 1 \leq v_i, w_i \leq n
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


n
v_1 w_1
v_2 w_2
:
v_{n-1} w_{n-1}


Output

If there is no permutation that can generate a tree isomorphic to Takahashi's favorite tree, print `-1`. If it exists, print the lexicographically smallest such permutation, with spaces in between.

Examples

Input

6
1 2
1 3
1 4
1 5
5 6


Output

1 2 4 5 3 6


Input

6
1 2
2 3
3 4
1 5
5 6


Output

1 2 3 4 5 6


Input

15
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15


Output

-1

### Response

```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

namespace asdfg
{
	const int N=101000;

	int begin[N],next[N*2],to[N*2];
	int fa[N],ind[N];

	int n,m,e,S,T;

	void add(int x,int y,bool k=1)
	{
		to[++e]=y;
		next[e]=begin[x];
		begin[x]=e;
		if(k)add(y,x,0);
	}
	int bfs(int p)
	{
		static std::queue<int> Q;

		for(int i=1;i<=n;i++)ind[i]=0;
		while(!Q.empty())Q.pop();

		int ret=-1;

		for(Q.push(p);!Q.empty();)
		{
			ret=p=Q.front(),Q.pop();
			ind[p]=1;
			for(int i=begin[p],q;i;i=next[i])
				if(!ind[q=to[i]])Q.push(q);
		}
		return ret;
	}
	void dfs(int p,int h=0)
	{
		fa[p]=h;
		for(int i=begin[p],q;i;i=next[i])
			if((q=to[i])!=h)dfs(q,p);
	}
	void initialize()
	{
		scanf("%d",&n);
		for(int i=1,u,v;i<n;i++)
			scanf("%d%d",&u,&v),add(u,v);

		T=bfs(S=bfs(1)),dfs(S);

		for(int i=1;i<=n;i++)ind[i]=0;
		for(int p=T;p;p=fa[p])ind[p]=++m;
	}
	bool check(int p)
	{
		for(int i=begin[p],q;i;i=next[i])
			if(ind[q=to[i]]==0)return 0;
		return 1;
	}
	int seq[N];
	bool judge()
	{
		for(int i=1;i<=m;i++)seq[i]=1;
		for(int p=T;p;p=fa[p])
		{
			for(int i=begin[p],q;i;i=next[i])
				if(ind[q=to[i]]==0)
				{
					if(!check(q))return 0;
					seq[ind[p]]++;
				}
		}
		return 1;
	}

	int s[N],t0[N],t1[N],t[N];

	void adjust()
	{
		for(int i=1;i<=n;i++)
			if(t0[i]!=t1[i])
			{
				if(t0[i]<t1[i])memcpy(t+i,t0+i,(n-i+1)*4);
				else memcpy(t+i,t1+i,(n-i+1)*4);
				break;
			}
			else t[i]=t0[i];
	}

	void work(int *ans)
	{
		int lst=0,tmp=0;
		for(int i=1;i<=m;i++)
		{
			s[++tmp]=lst+seq[i];
			for(int j=1;j<seq[i];j++)
				s[++tmp]=lst+j;
			lst+=seq[i];
		}
		for(int i=1;i<=n;i++)
			ans[s[i]]=i;
	}
	void solve()
	{
		initialize();
		if(!judge()){printf("-1\n");return;}

		work(t0);
		std::reverse(seq+1,seq+m+1);
		work(t1);

		adjust();

		for(int i=1;i<=n;i++)
			printf("%d ",t[i]);
		printf("\n");
	}
}

int main()
{
	asdfg::solve();
	return 0;
}

```