#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> G[100005];
vector<int> g[100005];
bool leaf[100005];
bool used[100005];
vector<int> vec, vec2, seq;

void dfs(int v, int prev, vector<int> &vec)
{
	vec.push_back(G[v].size());
	for(int i = 0; i < g[v].size(); i++){
		if(g[v][i] == prev) continue;
		dfs(g[v][i], v, vec);
	}
}

int main(void)
{
	cin >> n;
	int u, v;
	for(int i = 0; i < n-1; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	if(n == 2){
		cout << 1 << " " << 2 << endl;
		return 0;
	}
	for(int i = 1; i <= n; i++){
		if(G[i].size() == 1) leaf[i] = true;
	}
	for(int i = 1; i <= n; i++){
		if(leaf[i]) continue;
		for(int j = 0; j < G[i].size(); j++){
			if(!leaf[G[i][j]]) g[i].push_back(G[i][j]);
		}
	}
	
	for(int i = 1; i <= n; i++){
		if(!leaf[i] && g[i].size() >= 3){
			cout << -1 << endl;
			return 0;
		}
	}
	
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(leaf[i]) continue;
		if(g[i].size() <= 1){
			if(!cnt){
				dfs(i, -1, vec);
				cnt++;
			}else{
				dfs(i, -1, vec2);
				cnt++;
			}
		}
	}
	
	int res = 0;
	if(cnt == 2){
		for(int i = 0; i < vec.size(); i++){
			if(vec[i] < vec2[i]){
				res = 0;
				break;
			}
			if(vec[i] > vec2[i]){
				res = 1;
				break;
			}
		}
	}
	for(int i = 0; i < vec.size(); i++){
		seq.push_back( (res?vec2:vec)[i] );
	}
	seq.front(), seq.back()--;
	
	
	vector<int> cand, ans;
	cand.push_back(1);
	int nx = 2;
	for(int i = 0; i < seq.size(); i++){
		cand.push_back(nx);
		nx += seq[i]-1;
	}
	cand.push_back(n);
	
	for(int i = 0; i < cand.size(); i++) used[cand[i]] = true;
	reverse(cand.begin(), cand.end());
	int pre = n;
	for(int i = 0; i < cand.size(); i++){
		ans.push_back(cand[i]);
		for(int j = pre; j >= cand[i]; j--){
			if(!used[j]) ans.push_back(j);
		}
		pre = cand[i];
	}
	reverse(ans.begin(), ans.end());
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i] << " ";
	}
	cout << endl;
	
	return 0;
}

### Prompt

Generate 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 <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> G[100005];
vector<int> g[100005];
bool leaf[100005];
bool used[100005];
vector<int> vec, vec2, seq;

void dfs(int v, int prev, vector<int> &vec)
{
	vec.push_back(G[v].size());
	for(int i = 0; i < g[v].size(); i++){
		if(g[v][i] == prev) continue;
		dfs(g[v][i], v, vec);
	}
}

int main(void)
{
	cin >> n;
	int u, v;
	for(int i = 0; i < n-1; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	if(n == 2){
		cout << 1 << " " << 2 << endl;
		return 0;
	}
	for(int i = 1; i <= n; i++){
		if(G[i].size() == 1) leaf[i] = true;
	}
	for(int i = 1; i <= n; i++){
		if(leaf[i]) continue;
		for(int j = 0; j < G[i].size(); j++){
			if(!leaf[G[i][j]]) g[i].push_back(G[i][j]);
		}
	}
	
	for(int i = 1; i <= n; i++){
		if(!leaf[i] && g[i].size() >= 3){
			cout << -1 << endl;
			return 0;
		}
	}
	
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(leaf[i]) continue;
		if(g[i].size() <= 1){
			if(!cnt){
				dfs(i, -1, vec);
				cnt++;
			}else{
				dfs(i, -1, vec2);
				cnt++;
			}
		}
	}
	
	int res = 0;
	if(cnt == 2){
		for(int i = 0; i < vec.size(); i++){
			if(vec[i] < vec2[i]){
				res = 0;
				break;
			}
			if(vec[i] > vec2[i]){
				res = 1;
				break;
			}
		}
	}
	for(int i = 0; i < vec.size(); i++){
		seq.push_back( (res?vec2:vec)[i] );
	}
	seq.front(), seq.back()--;
	
	
	vector<int> cand, ans;
	cand.push_back(1);
	int nx = 2;
	for(int i = 0; i < seq.size(); i++){
		cand.push_back(nx);
		nx += seq[i]-1;
	}
	cand.push_back(n);
	
	for(int i = 0; i < cand.size(); i++) used[cand[i]] = true;
	reverse(cand.begin(), cand.end());
	int pre = n;
	for(int i = 0; i < cand.size(); i++){
		ans.push_back(cand[i]);
		for(int j = pre; j >= cand[i]; j--){
			if(!used[j]) ans.push_back(j);
		}
		pre = cand[i];
	}
	reverse(ans.begin(), ans.end());
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i] << " ";
	}
	cout << endl;
	
	return 0;
}

```