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 \le n \le 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 \le u,v \le 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]

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python
#-*- coding:utf-8 -*-

# Code by H~$~C

from sys import stdin
input = stdin.readline
import math

n = int(input())
G = [[] for i in range(n + 1)]
for i in range(n - 1):
  u, v = map(int, input().split())
  G[u].append([v, i])
  G[v].append([u, i])

ans = [-1] * (n + 1)

for u in range(1, n + 1):
  if (len(G[u]) >= 3):
    for j in range(len(G[u])):
      ans[G[u][j][1]] = j
    cnt = len(G[u])
    for j in range(n - 1):
      if (ans[j] == -1):
        ans[j] = cnt
        cnt += 1
    for j in range(n - 1):
      print(ans[j])
    return

for i in range(n - 1):
  print(i)

import sys
input = sys.stdin.readline

n=int(input())
E=[[] for i in range(n+1)]
D=dict()
DEG=[0]*(n+1)
for i in range(n-1):
    x,y=list(map(int,input().split()))
    E[x].append(y)
    E[y].append(x)
    D[x,y]=i
    D[y,x]=i
    DEG[x]+=1
    DEG[y]+=1

ANS=[-1]*(n-1)

LIST=[]
for i in range(n+1):
    if DEG[i]==1:
        LIST.append(i)

if len(LIST)==2:
    for i in range(n-1):
        print(i)

else:
    now=0
    for l in LIST:
        k=E[l][0]
        ANS[D[k,l]]=now
        now+=1

    #print(ANS)

    for i in range(n-1):
        if ANS[i]==-1:
            ANS[i]=now
            now+=1

    for a in ANS:
        print(a)




from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return map(int, data().split())
#sys.setrecursionlimit(100000)

n=int(input())
t=[dd(int) for i in range(n)]
l=[]
for i in range(n-1):
    u,v=mdata()
    t[u-1][v-1]=0
    t[v-1][u-1]=0
    l.append([u-1,v-1])
s=0
e=n-2
for i in range(n-1):
    a,b=l[i]
    if len(t[a])==1 or len(t[b])==1:
        print(s)
        s+=1
    else:
        print(e)
        e-=1

import sys
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
adj = [[] for _ in range(n)]
for i in range(n-1):
	u, v = map(int, input().split())
	adj[u-1].append((v-1, i))
	adj[v-1].append((u-1, i))

if max([len(x) for x in adj]) <= 2:
	print(*list(range(n-1)), sep="\n")
else:
	ans = [-1 for _ in range(n-1)]
	for i in range(n):
		if len(adj[i]) > 2:
			ans[adj[i][0][1]] = 0
			ans[adj[i][1][1]] = 1
			ans[adj[i][2][1]] = 2
			break
	tmp = 3
	for i in range(n-1):
		if ans[i] < 0:
			ans[i] = tmp
			tmp += 1
	print(*ans, sep="\n")


import sys
input = sys.stdin.readline


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]

tree = [[] for i in range(n)]
memo = {}
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    tree[a].append(b)
    tree[b].append(a)
    memo[a * 1000000 + b] = i
ans = [-1] * (n - 1)
pos = 0
for i in range(n):
    if len(tree[i]) == 1:
        a, b = i, tree[i][0]
        if a > b:
            a, b = b, a
        ans[memo[a * 1000000 + b]] = pos
        pos += 1
for i in range(n - 1):
    if ans[i] == -1:
        ans[i] = pos
        pos += 1
if n == 2:
    print(0)
    return
for i in ans:
    print(i)

import sys
input=sys.stdin.readline
n=int(input())
L=[[]for i in range(n)]
M=dict()
for i in range(n-1):
    a,b=map(int,input().split())
    M[i]=(a,b)
    L[a-1].append(b)
    L[b-1].append(a)
mxnode=-1
mxdeg=0
for j in range(n):
    if len(L[j])>mxdeg:
        mxdeg=len(L[j])
        mxnode=j+1
mxpt=0
normpt=0
mxedge=list(range(mxdeg))
noredg=list(range(mxdeg,n))
for j in range(n-1):
    if mxnode in M[j]:
        print(mxedge[mxpt])
        mxpt+=1
    else:
        print(noredg[normpt])
        normpt+=1