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;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const int N = 1e5 + 5;
const int lgN = 1e6 + 5;
const int te = 3e8 + 1;
const signed long long MOD = 998244353;
const long double pi = 3.141592653589793238462643383;
const signed long long IMAX = 1e9 + 5;
const double PI = 3.141592653589793;
template <class T>
using max_pq = priority_queue<T>;
template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T> >;
signed long long x, y;
template <class T>
T gcd(T a, T b) {
  if (a == 0) {
    x = 0, y = 1;
    return b;
  }
  T gc = gcd(b % a, a);
  T temp;
  temp = x;
  x = y - (b / a) * temp;
  y = temp;
  return gc;
}
signed long long po(signed long long a, signed long long x,
                    signed long long m) {
  if (x == 0) {
    return 1;
  }
  signed long long ans = 1;
  signed long long k = 1;
  while (k <= x) {
    if (x & k) {
      ans = ((ans * a) % m);
    }
    k <<= 1;
    a *= a;
    a %= m;
  }
  return ans;
}
signed long long modInverse(signed long long A, signed long long M) {
  gcd(A, M);
  return (x % M + M) % M;
}
int main() {
  signed long long n, i;
  cin >> n;
  vector<pair<signed long long, signed long long> > v(n - 1);
  vector<signed long long> cnt(n + 1);
  for (i = int(0); i <= int(n - 2); i++) {
    cin >> v[i].first >> v[i].second;
    cnt[v[i].first]++;
    cnt[v[i].second]++;
  }
  signed long long second = 0, e = n - 2;
  for (i = int(0); i <= int(n - 2); i++) {
    if (cnt[v[i].first] == 1 || cnt[v[i].second] == 1) {
      cout << second << "\n";
      ;
      second++;
    } else {
      cout << e << "\n";
      e--;
    }
  }
}
