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 PYTHON3):

Solution:
import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, = I()
g = [[] for i in range(n)]
edges = dd(int)
d = [0] * n
for i in range(n - 1):
    x, y = I()
    x -= 1; y -= 1
    g[x].append(y)
    g[y].append(x)
    if y < x:
        x, y = y, x
    edges[(x, y)] = i
    d[x] += 1
    d[y] += 1
ans = [-1] * n
v = dd(int)
mex = 0
if n == 2:
    print(0)
    exit()
for i in range(n):
    if d[i] == 1:
        e = tuple(sorted([i, g[i][0]]))
        ans[edges[e]] = mex
        mex += 1
for i in range(n - 1):
        if ans[i] == -1:
            ans[i] = mex
            mex += 1
        print(ans[i])