#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int N;
vector<vector<int>> G;
vector<int> d;

void dfs(int v,int p=-1){
	if(p!=-1) d[v] = d[p]+1;
	for(int u:G[v]) if(u!=p) dfs(u,v);
}
vector<int> calcdist(int r){
	d = vector<int>(N);
	dfs(r);
	return d;
}
int main(){
	cin>>N;
	G.resize(N);
	rep(i,N-1){
		int x,y;
		cin>>x>>y;
		x--,y--;
		G[x].pb(y);
		G[y].pb(x);
	}
	vector<int> d = calcdist(0);
	int a = 0;
	rep(i,N) if(d[i]>d[a]) a = i;
	d = calcdist(a);
	int b = 0;
	rep(i,N) if(d[i]>d[b]) b = i;

	vector<int> vs;
	{
		vs.pb(b);
		int v = b;
		while(v!=a){
			for(int u:G[v]) if(d[u]+1 == d[v]){
				v = u;
				break;
			}
			vs.pb(v);
		}
	}
	int L = vs.size();
	vector<int> c(L);
	rep1(i,L-2){
		int v = vs[i];
		for(int u:G[v]) if(u!=vs[i-1] && u!=vs[i+1]){
			if(G[u].size()!=1){
				puts("-1");
				return 0;
			}
			c[i]++;
		}
	}
	vector<int> rc = c;
	reverse(all(rc));
	if(c>rc) c = rc;

	int v = 1;
	rep(i,L){
		int ov = v;
		v++;
		rep(k,c[i]) cout<<v++<<" ";
		cout<<ov<<" ";
	}
	cout<<endl;
}

### Prompt

Your task is to create 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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int N;
vector<vector<int>> G;
vector<int> d;

void dfs(int v,int p=-1){
	if(p!=-1) d[v] = d[p]+1;
	for(int u:G[v]) if(u!=p) dfs(u,v);
}
vector<int> calcdist(int r){
	d = vector<int>(N);
	dfs(r);
	return d;
}
int main(){
	cin>>N;
	G.resize(N);
	rep(i,N-1){
		int x,y;
		cin>>x>>y;
		x--,y--;
		G[x].pb(y);
		G[y].pb(x);
	}
	vector<int> d = calcdist(0);
	int a = 0;
	rep(i,N) if(d[i]>d[a]) a = i;
	d = calcdist(a);
	int b = 0;
	rep(i,N) if(d[i]>d[b]) b = i;

	vector<int> vs;
	{
		vs.pb(b);
		int v = b;
		while(v!=a){
			for(int u:G[v]) if(d[u]+1 == d[v]){
				v = u;
				break;
			}
			vs.pb(v);
		}
	}
	int L = vs.size();
	vector<int> c(L);
	rep1(i,L-2){
		int v = vs[i];
		for(int u:G[v]) if(u!=vs[i-1] && u!=vs[i+1]){
			if(G[u].size()!=1){
				puts("-1");
				return 0;
			}
			c[i]++;
		}
	}
	vector<int> rc = c;
	reverse(all(rc));
	if(c>rc) c = rc;

	int v = 1;
	rep(i,L){
		int ov = v;
		v++;
		rep(k,c[i]) cout<<v++<<" ";
		cout<<ov<<" ";
	}
	cout<<endl;
}

```