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

def calcdist(adj_list, visited, stack, d):
    node = stack.pop()
    if visited[node]:
        return
    visited[node] = True
    for e in adj_list[node]:
        if visited[e] == False:
            stack.append(e)
            d[e] = d[node] + 1
    return

def answer(n, u, v):
    if n == 2:
        print(0)
        return
    
    adj_list = [[] for _ in range(n+1)] #first [] will never be filled.
    for i in range(n-1):
        adj_list[v[i]].append(u[i])
        adj_list[u[i]].append(v[i])
    leaf = [False for _ in range(n+1)]
    label = [10**6 for _ in range(n+1)]
    next_label = 0
    for i in range(1, n+1):
        if len(adj_list[i]) == 1:
            leaf[i] = True
            label[i] = next_label
            next_label += 1
    root = 0
    for i in range(1, n+1):
        if leaf[i] == False:
            label[i] = next_label
            next_label += 1
            root = i
    
    #print('label=', label)
    visited = [False for _ in range(n+1)] #node 0 False forever. Only 1-n of interest.
    stack = [root]
    d = [0 for _ in range(n+1)]
    while len(stack) > 0:
        calcdist(adj_list, visited, stack, d)
    
    #print('d=', d)
    for i in range(n-1):
        if d[v[i]] > d[u[i]]:
            print(label[v[i]])
        else:
            print(label[u[i]])
    
    return

def main():
    n = int(sys.stdin.readline())
    u = [0 for i in range(n-1)]
    v = [0 for i in range(n-1)]
    for i in range(n-1):
        u[i], v[i] = map(int, sys.stdin.readline().split())
    answer(n, u, v)
    return
main()