#include <bits/stdc++.h>

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int maxN = 1e5 + 10;

vector <int> adj[maxN];
int h[maxN], par[maxN];

void DFS(int v, int p = -1)
{
	par[v] = p;
	for (auto u : adj[v])
		if(u != p){
			h[u] = h[v] + 1;
			DFS(u, v);
		}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for (int i=0; i<n-1; i++)
	{
		int u, v; cin >> u >> v;
		u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}

	DFS(0);

	int mx = -1, v = 0, u = 0;
	for (int i=0; i<n; i++)
		if(h[i] > mx) mx = h[i], v = i;
	
	h[v] = 0;
	DFS(v);


	mx = -1;
	for (int i=0; i<n; i++)
		if(h[i] > mx) mx = h[i], u = i;
	
	//cout << v << ',' << u << " ---> " << h[u] << endl;

	int sum = 0;

	int curr = u;
	while(curr != -1)
	{
		sum += (int)adj[curr].size();
		curr = par[curr];
	}

	sum -= 2 * h[u];

	if(sum != n - h[u] - 1) return cout << -1 << endl, 0;

	vector <int> v1, v2;

	curr = u;
	int now = 0;

	while(curr != -1)
	{
		now ++;
		if(adj[curr].size() == 1) v1.pb(now);
		else
		{
			int d = (int)adj[curr].size() - 2;
			for (int j=0; j<d; j++) v1.pb(now + j + 1);
			v1.pb(now);
			now += d;
		}
		curr = par[curr];
		

	}

	h[u] = 0; DFS(u);

	curr = v;
	now = 0;
	while(curr != -1)
	{
		now ++;
		if(adj[curr].size() == 1) v2.pb(now);
		else
		{
			int d = (int)adj[curr].size() - 2;
			for (int j=0; j<d; j++) v2.pb(now + j + 1);
			v2.pb(now);
			now += d;
		}
		curr = par[curr];
	}

	for (int i=0; i<n; i++)
		if(v1[i] < v2[i])
		{
			for (int j=0; j<n; j++) cout << v1[j] << ' ';
			cout << endl;
			return 0;
		}else if(v1[i] > v2[i])
		{
			for (int j=0; j<n; j++) cout << v2[j] << ' ';
			cout << endl;
			return 0;
		}

	for (int j=0; j<n; j++) cout << v1[j] << ' ';
	cout << endl;

}
### Prompt

Construct a CPP code solution to the problem outlined:

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 F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int maxN = 1e5 + 10;

vector <int> adj[maxN];
int h[maxN], par[maxN];

void DFS(int v, int p = -1)
{
	par[v] = p;
	for (auto u : adj[v])
		if(u != p){
			h[u] = h[v] + 1;
			DFS(u, v);
		}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for (int i=0; i<n-1; i++)
	{
		int u, v; cin >> u >> v;
		u--; v--;
		adj[u].pb(v); adj[v].pb(u);
	}

	DFS(0);

	int mx = -1, v = 0, u = 0;
	for (int i=0; i<n; i++)
		if(h[i] > mx) mx = h[i], v = i;
	
	h[v] = 0;
	DFS(v);


	mx = -1;
	for (int i=0; i<n; i++)
		if(h[i] > mx) mx = h[i], u = i;
	
	//cout << v << ',' << u << " ---> " << h[u] << endl;

	int sum = 0;

	int curr = u;
	while(curr != -1)
	{
		sum += (int)adj[curr].size();
		curr = par[curr];
	}

	sum -= 2 * h[u];

	if(sum != n - h[u] - 1) return cout << -1 << endl, 0;

	vector <int> v1, v2;

	curr = u;
	int now = 0;

	while(curr != -1)
	{
		now ++;
		if(adj[curr].size() == 1) v1.pb(now);
		else
		{
			int d = (int)adj[curr].size() - 2;
			for (int j=0; j<d; j++) v1.pb(now + j + 1);
			v1.pb(now);
			now += d;
		}
		curr = par[curr];
		

	}

	h[u] = 0; DFS(u);

	curr = v;
	now = 0;
	while(curr != -1)
	{
		now ++;
		if(adj[curr].size() == 1) v2.pb(now);
		else
		{
			int d = (int)adj[curr].size() - 2;
			for (int j=0; j<d; j++) v2.pb(now + j + 1);
			v2.pb(now);
			now += d;
		}
		curr = par[curr];
	}

	for (int i=0; i<n; i++)
		if(v1[i] < v2[i])
		{
			for (int j=0; j<n; j++) cout << v1[j] << ' ';
			cout << endl;
			return 0;
		}else if(v1[i] > v2[i])
		{
			for (int j=0; j<n; j++) cout << v2[j] << ' ';
			cout << endl;
			return 0;
		}

	for (int j=0; j<n; j++) cout << v1[j] << ' ';
	cout << endl;

}
```