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 Counter, OrderedDict
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math

g   = lambda : stdin.readline().strip()
gl  = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1e9)+7
inf = float("inf")

n, = gil()
edges = OrderedDict()
adj = [[] for _ in range(n+1)]
for _ in range(n-1):
	x, y = gil()
	edges[(x, y)] = None
	edges[(y, x)] = None
	adj[x].append(y)
	adj[y].append(x)

dp = [1]*(n+1); vis = [0]*(n+1) ; fin = [0]*(n+1)

stack = [1]

while stack :
	node = stack[-1]
	if vis[node]:
		for c in adj[node]:
			if fin[c] : dp[node]+=dp[c]
		fin[node] = 1
		stack.pop()
	else:
		vis[node] = 1
		for c in adj[node]:
			if vis[c] == 0:
				stack.append(c)
vis = [0]*(n+1)
stack = [1]
costs = []
while stack :
	node = stack.pop()
	vis[node] = 1
	for c in adj[node]:
		if vis[c] == 0 :
			stack.append(c)
			costs.append((dp[c]*(n-dp[c]), node, c))


costs.sort(key = lambda x : x[0], reverse=True)
val = n-2
for _, x, y in costs:
	edges[x, y] = val
	val -= 1

for val in edges.values():
	if val is not None :
		print(val)
