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 as dd
from collections import deque
import sys
sys.setrecursionlimit(pow(10,5))
input = sys.stdin.readline

def count_leaf(tree,degree,visited,i):
	#print(degree)
	visited[i] = True
	for k in tree[i]:
		if visited[k] == False:
			degree[i]+=1
			degree[k]+=1
			count_leaf(tree,degree,visited,k)



def main():
	
	tree = dd(list)
	t = int(input())
	inpu = []
	for i in range(t-1):
		a,b = map(int,input().split())
		inpu.append((a,b))
		tree[a].append(b)
		tree[b].append(a)
	leafes = []
	#count_leaf(tree,degree,visited,1)
	for i in tree:
		if len(tree[i]) == 1:
			leafes.append(i)
	#print(leafes)
	leaf = deque()
	non_leaf = deque()

	for i in range(len(leafes)):
		leaf.append(i)
	for i in range(len(leafes),t):
		non_leaf.append(i)

	#print(leafes)
	#print(leaf)
	#print(non_leaf)
	#print(inpu)
	for i in inpu:
		if len(tree[i[0]]) == 1 or len(tree[i[1]]) == 1:
			print(leaf.popleft())
		else:
			print(non_leaf.popleft())

 
		

main()