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>
import sys
N = int(input())
if N == 2:
    print(0)
    sys.exit(0)

degree = [0 for _ in range(N+1)]
adj_list = [[] for _ in range(N+1)]

edges = []

leaves = []
for _ in range(N-1):
    [u,v] = list(map(int,input().split()))
    adj_list[u].append(v)
    adj_list[v].append(u)
    edges.append((u,v))
for n in range(1,N+1):
    if len(adj_list[n]) == 1:
        leaves.append(n)

labels = {}
l0 = leaves[0]
(u0,v0) = (l0, adj_list[l0][0])
labels[(u0,v0)] = 0
labels[(v0,u0)] = 0

l1 = leaves[1]
(u1,v1) = (l1, adj_list[l1][0])
labels[(u1,v1)] = 1
labels[(v1,u1)] = 1

ctr = 2
if len(leaves) > 2:
    l2 = leaves[-1]
    (u,v) = (l2, adj_list[l2][0])
    labels[(u,v)] = 2
    labels[(v,u)] = 2
    ctr += 1

for (u,v) in edges:
    if (u,v) in labels:
        print(labels[(u,v)])
    else:
        print(ctr)
        ctr+=1

