C. Ehab and Path-etic MEXs

链接：https://codeforces.ml/contest/1325/problem/C

You are given a tree consisting of nn nodes. You want to write some labels on the tree's edges such that the following conditions hold:

• Every label is an integer between 00 and n−2n−2 inclusive.
• All the written labels are distinct.
• The largest value among MEX(u,v)MEX(u,v) over all pairs of nodes (u,v)(u,v) is as small as possible.

Here, MEX(u,v)MEX(u,v) denotes the smallest non-negative integer that isn't written on any edge on the unique simple path from node uu to node vv.

Input

The first line contains the integer nn (2≤n≤1052≤n≤105) — the number of nodes in the tree.

Each of the next n−1n−1 lines contains two space-separated integers uu and vv (1≤u,v≤n1≤u,v≤n) that mean there's an edge between nodes uuand vv. It's guaranteed that the given graph is a tree.

Output

Output n−1n−1 integers. The ithith of them will be the number written on the ithith edge (in the input order).

Examples

input

Copy

3
1 2
1 3

output

Copy

0
1

input

Copy

6
1 2
1 3
2 4
2 5
5 6

output

Copy

0
3
2
4
1

Note

The tree from the second sample:

正在上传…重新上传取消

主要难在读题。。。

#include<bits/stdc++.h>
using namespace std;
long long n,t,k,s,u[100005],v[100005];
map<long long,long long>m;
long long a[1000001];
int main()
{
	cin>>n;
	int k=0;
	for(int i=1;i<=n-1;i++)
	{
		cin>>u[i]>>v[i];
		m[u[i]]++;
		m[v[i]]++;
		a[i]=-1;
	}
	int j=n-2;
	for(int i=1;i<=n-1;i++)
	{
		if(m[u[i]]==1||m[v[i]]==1)
		continue;
		else
		{
			a[i]=j;
			j--;
		}
	}
	for(int i=1;i<=n-1;i++)
	{
		if(a[i]==-1)
		{
			a[i]=j;
			j--;
		}
	}
	for(int i=1;i<=n-1;i++)
	cout<<a[i]<<endl;
}