Codeforces Round #628 (Div. 2)C. Ehab and Path-etic MEXs

C. Ehab and Path-etic MEXs
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a tree consisting of n nodes. You want to write some labels on the tree’s edges such that the following conditions hold:

Every label is an integer between 0 and n−2 inclusive.
All the written labels are distinct.
The largest value among MEX(u,v) over all pairs of nodes (u,v) is as small as possible.
Here, MEX(u,v) denotes the smallest non-negative integer that isn’t written on any edge on the unique simple path from node u to node v.

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

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

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

Examples
inputCopy
3
1 2
1 3
outputCopy
0
1
inputCopy
6
1 2
1 3
2 4
2 5
5 6
outputCopy
0
3
2
4
1
Note
The tree from the second sample:

思路：考虑两种极端情况把
第一种 如果树退化成链，那么其实不用管，不论怎么输出mex最大值都是一样的 都是n-1
因为链的两个端点之间 一定是从0-n-2所有数 所以mex一定是n-1
第二种 就是考虑只有一个父节点，第二层都是子节点，也就是说父节点出度为n-1，其他点入度为1 这样子的mex最大值最小是2，因为任意两点之间最多经过2个点，推广到不是第一种极端情况的所有情况，其实mex的最大值最小一定是2，只要保证0 1 2三个点不在同一条链上即可
所以问题转化成怎么让0 1 2不形成一个链，考虑度，如果一个点k，有三个边与他相连，我们把0 1 2放再他的三个相连边即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
int d[100005];
paii v[100005];
bool vis[100005];
int main()
{
   int n;cin>>n;
   rep(i,1,n){
      cin>>v[i].x>>v[i].y;
      d[v[i].y]++;
      d[v[i].x]++;
   }
    int k=0;
    repd(i,1,n){
       if(d[i]>=3){
           k=i;
           break;
       }
    }
    if(k==0){
        rep(i,1,n) cout<<i-1<<endl;
    }
    else
    {
        int num=0,q=3;
        rep(i,1,n){
          if(num<3 && (v[i].x==k || v[i].y==k)){
            cout<<num<<endl;
            num++;
          }
          else cout<<q++<<endl;
        }
    }
   return 0;
}