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
Input
3
1 2
1 3
Output
0
1
Input
6
1 2
1 3
2 4
2 5
5 6
Output
0
3
2
4
1
Note
The tree from the second sample:

思路：挺考驗(yàn)思維的一道題目。我們可以想一下，0和1一定是可以在同一路徑上的，因此最小價(jià)值一定大于等于2.那么我們就盡可能的去往2上靠。要想是2的話，那么0,1,2肯定不能在同一路徑上，這樣的話，我們找到一個(gè)度大于等于3的點(diǎn)，然后安排上0,1,2，剩下的隨便放置，就可以了。對(duì)于沒有度數(shù)大于等于3的點(diǎn)來(lái)說(shuō)，就是一條鏈，最終結(jié)果肯定是n-1了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; struct node{int x,y; }p[maxx]; vector<int> v[maxx]; int n;inline void init() {for(int i=1;i<=n;i++) v[i].clear(); } int main() {scanf("%d",&n);init();for(int i=1;i<n;i++){scanf("%d%d",&p[i].x,&p[i].y);v[p[i].x].push_back(p[i].y);v[p[i].y].push_back(p[i].x);}map<pair<int,int>,int> mp;mp.clear();int cnt=0;for(int i=1;i<=n;i++){if(v[i].size()>=3){for(int j=0;j<3;j++) mp[make_pair(i,v[i][j])]=++cnt;break;}}for(int i=1;i<n;i++){if(mp[make_pair(p[i].x,p[i].y)]) cout<<mp[make_pair(p[i].x,p[i].y)]-1<<endl;else if(mp[make_pair(p[i].y,p[i].x)]) cout<<mp[make_pair(p[i].y,p[i].x)]-1<<endl;else cout<<cnt++<<endl;}return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的Ehab and Path-etic MEXs CodeForces - 1325C（思维+贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。