Problem: 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 ≤ 10^5) — 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 i^{th} of them will be the number written on the i^{th} 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:

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
using namespace std;
const int maxn = 200001;
using large = int64_t;
long long gcd(long long int a, long long int b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long x1, y1;
  long long d = gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - y1 * (a / b);
  return d;
}
vector<int> v[maxn];
map<pair<int, int>, int> mp;
int ans[maxn];
int a, b, p = 0;
void dfs(int node, int par) {
  for (int child : v[node]) {
    if (child != par) dfs(child, node);
  }
  if (par != 0) {
    if (v[node].size() > 1 && v[par].size() > 1 &&
        p < (v[node].size() - 2 + v[par].size())) {
      a = node;
      b = par;
      p = v[node].size() - 2 + v[par].size();
    }
  }
}
int main() {
  int t;
  long long i, j, k, l, m, n;
  cin >> n;
  for (i = 1; i < n; i++) {
    cin >> j >> k;
    v[j].push_back(k);
    v[k].push_back(j);
    a = k;
    b = j;
    mp[{j, k}] = mp[{k, j}] = i;
  }
  memset(ans, -1, sizeof(ans));
  dfs(1, 0);
  j = 0;
  ans[mp[{a, b}]] = j++;
  if (v[a].size() < v[b].size()) swap(a, b);
  for (int child : v[a]) {
    if (child != b) {
      ans[mp[{a, child}]] = j++;
    }
  }
  for (int child : v[b]) {
    if (child != a) {
      ans[mp[{b, child}]] = j++;
    }
  }
  for (i = 1; i < n; i++) {
    if (ans[i] == -1) ans[i] = j++;
  }
  for (i = 1; i < n; i++) {
    cout << ans[i] << "\n";
  }
}