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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class c_628 {

	static ArrayList adj [];
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub

		FastScanner in = new FastScanner(System.in);
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		
		int N = in.nextInt();
		
		adj = new ArrayList [N];
		int edge [][] = new int [N-1][2];
		int deg [] = new int [N];
		
		
		for(int i = 0; i < N; i++) {
			adj[i] = new ArrayList<Integer> ();
		}
		
		for(int i = 0; i < N-1; i++) {
			edge[i][0] = in.nextInt() - 1;
			edge[i][1] = in.nextInt() - 1;
			
			
			deg[edge[i][0]]++;
			deg[edge[i][1]]++;
		}

		
		boolean leaf [] = new boolean [N];
		for(int i = 0; i < N; i++) {
			if(deg[i] == 1) leaf[i] = true;
		}
		
		int val [] = new int [N-1];
		int lo = 0;
		int hi = N-2;
		
		for(int i = 0; i < N-1; i++) {
			if(leaf[edge[i][0]] || leaf[edge[i][1]]) {
				val[i] = lo;
				lo++;
			}else {
				val[i] = hi;
				hi--;
			}
			out.println(val[i]);
		}
		
		out.close();
	}

	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(InputStream stream) {
			br = new BufferedReader(new InputStreamReader(stream));
			st = new StringTokenizer("");
		}

		public FastScanner(String fileName) throws Exception {
			br = new BufferedReader(new FileReader(new File(fileName)));
			st = new StringTokenizer("");
		}

		public String next() throws Exception {
			while (!st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return st.nextToken();
		}

		public int nextInt() throws Exception {
			return Integer.parseInt(next());
		}

		public long nextLong() throws Exception {
			return Long.parseLong(next());
		}

		public Double nextDouble() throws Exception {
			return Double.parseDouble(next());
		}

		public String nextLine() throws Exception {
			if (st.hasMoreTokens()) {
				StringBuilder str = new StringBuilder();
				boolean first = true;
				while (st.hasMoreTokens()) {
					if (first) {
						first = false;
					} else {
						str.append(" ");
					}
					str.append(st.nextToken());
				}
				return str.toString();
			} else {
				return br.readLine();
			}
		}
	}

	
}