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>
from collections import defaultdict
from collections import deque
n = int(raw_input().strip())
tree = defaultdict(list)
edge = []
edge_val = dict()
for i in range(n - 1):
    a,b = map(int,raw_input().strip().split())
    tree[a].append(b)
    tree[b].append(a)
    edge.append((a,b))
root = 1
for i in range(1,n + 1):
    if len(tree[i]) <= 1:
        root = i
        break

edge_val[(root,tree[root][0])] = 0
q = deque()
visited = set()
visited.add(root)
has = False
for node in tree[root]:
    if node != root:
        q.append(node)

while len(q) != 0:
    next_node = q.popleft()
    visited.add(next_node)
    if len(tree[next_node]) > 2:
        cnt = 1
        for added in tree[next_node]:
            if cnt == 3:
                break
            if added not in visited:
                edge_val[(next_node,added)] = cnt
                cnt += 1
        has = True
        break
    else:
        for child in tree[next_node]:
            if child not in visited:
                q.append(child)
if n == 3:
    print 0
    print 1
else:
    if has:
        cnt = 3
        for each_edge in edge:
            a,b = each_edge
            #print(each_edge)
            if (a,b) in edge_val: 
                print edge_val[(a,b)]
                #print(111)
            elif (b,a) in edge_val:
                print edge_val[(b,a)] 
                #print(222)
            else:
                print cnt
                #print(333)
                cnt += 1
    else:
        cnt = 0
        for each_edge in edge:
            print cnt 
            cnt += 1

