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 time,math
from sys import stdin,stdout
from collections import deque
import bisect
from fractions import Fraction
pi=3.14159265358979323846264338327950
def I():
    return (stdin.readline())
def In():
    return map(int,stdin.readline().split())
def L():
    return list(map(int,stdin.readline().split()))
def Si():
    return sorted(list(map(int,stdin.readline().split())))
def Si():
    return sorted(list(map(int,stdin.readline().split())),reverse=True)
def P(x):
    return stdout.write(str(x)+"\n")
def Pi(x,y):
    return stdout.write(str(x)+" "+str(y)+"\n")
def lcm(a,b):
    return (a*b)//gcd(a,b)
def gcd(a,b):
    if a==0:
        return b
    elif b==0:
        return a
    if a>b:
        return gcd(a%b,b)
    else:
        return gcd(a,b%a)
def readTree():
    v=int(input())
    li=[set() for i in range(v+1)]
    l=[]
    for i in range(v-1):
        u1,u2=In()
        li[u1].add(u2)
        li[u2].add(u1)
        l.append([u1,u2])
    return li,v,l
#####################################################################################

def bfs(adj,v):
    visited=[False]*(v+1)
    visited[1]=True
    q=deque()
    q.append(1)
    while q:
        ele=q.pop()
        if len(adj[ele])>=3:
            note=ele
            return True,note
        for sml in adj[ele]:
            if visited[sml]==False:
                q.append(sml)
                visited[sml]=True
    return False,-1

def solve():
    adj,v,l=readTree()
    stm,val=bfs(adj,v)
    if stm==False:
        li=[i for i in range(v-1)]
        for ele in li:
            P(ele)
    else:
        u=[0,1,2]
        avail=[i for i in range(3,v-1)]
        for ele in l:
            u1,u2=ele[0],ele[1]
            if u1==val or u2==val:
                if u:
                    print(u.pop())
                else:
                    print(avail.pop())
            else:
                print(avail.pop())
solve()