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>
#include <bits/stdc++.h>
using namespace std;
bool *Seive(long long n, bool *p) {
  memset(p, 1, sizeof(p));
  long long i, j;
  for (i = 2; i <= n; i++) {
    if (p[i] == 1)
      for (j = i * i; j <= n; j += i) {
        p[j] = 0;
      }
  }
  p[1] = 0;
  return p;
}
long long gcd(long long a, long long b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long modexp(long long x, long long y) {
  if (y == 0)
    return 1;
  else if (y % 2 == 0) {
    return modexp((x * x) % (long long)(1e9 + 7), y / 2);
  } else {
    return (x * modexp((x * x) % (long long)(1e9 + 7), (y - 1) / 2)) %
           (long long)(1e9 + 7);
  }
}
long long fact(long long n) {
  long long f = 1;
  for (long long i = 2; i <= n; i++) {
    f = (i % (long long)(1e9 + 7) * f % (long long)(1e9 + 7)) %
        (long long)(1e9 + 7);
  }
  return f;
}
long long nCr(long long n, long long r) {
  return (fact(n) * modexp((fact(n - r) * fact(r)) % (long long)(1e9 + 7),
                           (long long)(1e9 + 7) - 2)) %
         (long long)(1e9 + 7);
}
void showlist(list<int64_t> g) {
  list<int64_t>::iterator it;
  for (it = g.begin(); it != g.end(); ++it) cout << *it << " ";
  cout << '\n';
}
void swap(int64_t &a, int64_t &b) {
  int64_t t;
  t = a;
  a = b;
  b = t;
}
void build(int64_t l, int64_t r, int64_t i) {
  if (l == r) {
  } else {
    int64_t mid = (l + r) / 2;
    build(l, mid, 2 * i);
    build(mid + 1, r, 2 * i + 1);
  }
}
void update(int64_t p, int64_t l, int64_t r, int64_t i) {
  if (l == r) {
  } else {
    int64_t mid = (l + r) / 2;
    if (p <= mid) {
      update(p, l, mid, 2 * i);
    } else {
      update(p, mid + 1, r, 2 * i + 1);
    }
  }
}
void query(int64_t y, int64_t z, int64_t l, int64_t r, int64_t i) {
  if (y <= l && z >= r) {
  } else {
    int64_t mid = (l + r) / 2;
    if (z <= mid) {
      query(y, z, l, mid, 2 * i);
    } else if (y > mid) {
      query(y, z, mid + 1, r, 2 * i + 1);
    } else {
      query(y, z, l, mid, 2 * i);
      query(y, z, mid + 1, r, 2 * i + 1);
    }
  }
}
void make_set(int64_t v) {}
int64_t find_set(int64_t v) {}
void union_sets(int64_t a, int64_t b) {}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int64_t n, i, j;
  cin >> n;
  vector<vector<int64_t>> adj(n + 1);
  int64_t x[n - 1], y[n - 1];
  map<pair<int64_t, int64_t>, int64_t> m;
  for (i = 0; i < n - 1; i++) {
    cin >> x[i] >> y[i];
    m.insert(make_pair(make_pair(x[i], y[i]), i));
    m.insert(make_pair(make_pair(y[i], x[i]), i));
    adj[x[i]].push_back(y[i]);
    adj[y[i]].push_back(x[i]);
  }
  int64_t ans[n - 1];
  memset(ans, -1, sizeof(ans));
  int64_t f = 0;
  for (i = 1; i <= n; i++) {
    if (adj[i].size() >= 3) {
      for (j = 0; j < 3; j++) {
        int64_t g;
        g = m[make_pair(adj[i][j], i)];
        ans[g] = f++;
      }
      break;
    }
  }
  for (i = 0; i < n - 1; i++) {
    if (ans[i] == -1) {
      ans[i] = f++;
    }
    cout << ans[i] << "\n";
  }
  return 0;
}
