#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n;
vector<int> e[100010];

int hashi[100010], hn;

char vis[100010];

void dfs(int x){
	vis[x]=1;
	int ic = 0;
	for(int y:e[x]) if(e[y].size() != 1u){
		++ic;
		if(!vis[y]) dfs(y);
	}
	if(ic >= 3){ puts("-1"); exit(0); }
	if(ic <= 1){
		hashi[hn++] = x;
	}
}

int cp[100010];
int np[100010], npp;

void Make(int x){
	int lc = 0;
	vis[x] = 1;
	int nxt = -1;
	for(int y:e[x]) if(!vis[y]){
		if(e[y].size() == 1u) ++lc;
		else nxt = y;
	}
	for(int i=1; i<=lc; ++i) np[npp+i] = npp+i+1;
	np[npp + lc + 1] = npp + 1;
	npp += lc + 1;
	if(nxt != -1) Make(nxt);
	else if(lc >= 1) swap(np[n-1], np[n]);
}

void Prep(){
	fill(vis+1, vis+n+1, 0); npp=0;
}
void Upd(){
	for(int i=1; i<=n; ++i){
		if(cp[i] < np[i]) break;
		else if(cp[i] > np[i]){
			for(int j=i; j<=n; ++j) cp[j]=np[j];
			break;
		}
	}
}

int main()
{
	read(n);
	if(n == 2){ puts("1 2"); return 0; }
	for(int i=1; i<n; ++i){
		int a, b; read(a, b);
		e[a].pb(b); e[b].pb(a);
	}
	
	for(int i=1; i<=n; ++i) if(e[i].size() != 1u){ dfs(i); break; }
	if(hn > 2){ puts("-1"); return 0; }
	
	for(int i=1; i<=n; ++i) cp[i]=n+1-i;
	for(int a=0; a<hn; ++a){
		Prep(); Make(hashi[a]); Upd();
		for(int p:e[hashi[a]]) if(e[p].size() == 1u){
			Prep(); Make(p); Upd();
			break;
		}
	}
	
	for(int i=1; i<=n; ++i) printf("%d ", cp[i]);
	return 0;
}

### Prompt

Your challenge is to write a Cpp solution to 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n;
vector<int> e[100010];

int hashi[100010], hn;

char vis[100010];

void dfs(int x){
	vis[x]=1;
	int ic = 0;
	for(int y:e[x]) if(e[y].size() != 1u){
		++ic;
		if(!vis[y]) dfs(y);
	}
	if(ic >= 3){ puts("-1"); exit(0); }
	if(ic <= 1){
		hashi[hn++] = x;
	}
}

int cp[100010];
int np[100010], npp;

void Make(int x){
	int lc = 0;
	vis[x] = 1;
	int nxt = -1;
	for(int y:e[x]) if(!vis[y]){
		if(e[y].size() == 1u) ++lc;
		else nxt = y;
	}
	for(int i=1; i<=lc; ++i) np[npp+i] = npp+i+1;
	np[npp + lc + 1] = npp + 1;
	npp += lc + 1;
	if(nxt != -1) Make(nxt);
	else if(lc >= 1) swap(np[n-1], np[n]);
}

void Prep(){
	fill(vis+1, vis+n+1, 0); npp=0;
}
void Upd(){
	for(int i=1; i<=n; ++i){
		if(cp[i] < np[i]) break;
		else if(cp[i] > np[i]){
			for(int j=i; j<=n; ++j) cp[j]=np[j];
			break;
		}
	}
}

int main()
{
	read(n);
	if(n == 2){ puts("1 2"); return 0; }
	for(int i=1; i<n; ++i){
		int a, b; read(a, b);
		e[a].pb(b); e[b].pb(a);
	}
	
	for(int i=1; i<=n; ++i) if(e[i].size() != 1u){ dfs(i); break; }
	if(hn > 2){ puts("-1"); return 0; }
	
	for(int i=1; i<=n; ++i) cp[i]=n+1-i;
	for(int a=0; a<hn; ++a){
		Prep(); Make(hashi[a]); Upd();
		for(int p:e[hashi[a]]) if(e[p].size() == 1u){
			Prep(); Make(p); Upd();
			break;
		}
	}
	
	for(int i=1; i<=n; ++i) printf("%d ", cp[i]);
	return 0;
}

```