本文共 1783 字，大约阅读时间需要 5 分钟。

C. Ehab and Path-etic MEXs

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 uu and 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

31 21 3

output

Copy

01

input

Copy

61 21 32 42 55 6

output

Copy

03241

Note

The tree from the second sample:

【题意】

给出n个点，n-1条边，，给每条边赋值，，[0~n-2]，使得任意两点之间的MEX最大值最小。

MEX指的是集合中未出现的最小非负整数。

【思路】

其实只要没有度数大于3的节点，，这棵树就可以退化成链，， 链的两个端点之间 一定是从0-n-2所有数 所以mex一定是n-1。

要是有一个大于3的点，，在他所连接的三条边上分别赋值0，1，2，，其余的就随便了，输出即可。。

#include 
   
    using namespace std;int d[100005];pair
    
     pi[100005];int main(){     ios::sync_with_stdio(false);     int n;     cin>>n;     for(int i=1;i<=n-1;i++)     {        cin>>pi[i].first>>pi[i].second;        d[pi[i].first]++;        d[pi[i].second]++;     }     int k=0;     for(int i=1;i<=n;i++)     {         if(d[i]>=3)         {             k=i;             break;         }     }     if(k==0)     {         for(int i=1;i
    
   

转载地址：http://otyzi.baihongyu.com/