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:


# from math import factorial as fac
from collections import defaultdict
# from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
# print(f.readline())
# sys.setrecursionlimit(10**5)

	
def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline().strip())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())


def solution(A,n,d):
	leaves = [x for x in d if d[x] == 1]
	if len(leaves)  == 2:
		return '\n'.join(map(str,range(n-1)))
	s = ''
	cnt = 0 
	other_cnt = 3
	si = set()
	for x,y in A:
		if (d[x] == 1 or d[y] == 1) and cnt < 3:
			si.add(cnt)
			s+=str(cnt)+'\n'
			cnt+=1
		else:
			si.add(other_cnt)
			s+=str(other_cnt)+'\n'
			other_cnt+=1
	# assert cnt == 3 
	# assert other_cnt == n-1
	return s



def main():
	T = 1
	for i in range(T):
		n = read_int()
		d = defaultdict(int)
		A = []
		for j in range(n-1):
			A.append(read_int_array())
			d[A[-1][0]]+=1
			d[A[-1][1]]+=1
			# print(j)
		# continue
		x = solution(A,n,d)

		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			print >>output,str(x)# "Case #"+str(i+1)+':',
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()

if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
#example usage:
#    for l in res:
#       print >>output, str(len(l)) + ' ' +  ' '.join(l)

if __name__ == '__main__':
	main()



'''stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* BITS - THINK HOW TO MASK PROPERLY
	* PERMUTATIONS - PARITY AND CYCLES
	* Think simple, if it becomes over complicated, try to look at it from a different perspective.
	* Have fun!!!
	* TRY FIXING SOMETHING, and then maybe binary search around it.
	* Remember heaps. 
	* Remember how to add a value to a segment when using prefix sum.
		suppose you have an array[1,2,3,4,5] and you want to add 3 to array[1:4]. Then just 
		add 3 to A[1], and decrease 3 from A[4]. Let's look at what happens:
		original prefixsums is 					 [1,3,6,10,15]
		array -> [1,5,3,4,2] and prefix sums are [1,6,9,13,15] 
		As you see, exactly +3 in A[1:4]
		*** The previous method can help checking how many x,y you can choose to get s=x+y from two arrays.
'''
'''
binary search 
	while(r - l > 1) {
		ll mid = l + (r - l) / 2;
		solve(mid);
		ll sum = 0;
		for (int i = 0; i < n; i++)
			sum += b[i];
		if (sum <= k)
			r = mid;
		else
			l = mid;
	}
'''