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.util.*;
import java.lang.*;
import java.io.*;

public class feb20 {

//	            ***                          ++                      
//             +=-==+                      +++=-                     
//            +-:---==+                   *+=----=                   
//           +-:------==+               ++=------==                  
//           =-----------=++=========================                
//          +--:::::---:-----============-=======+++====             
//          +---:..:----::-===============-======+++++++++           
//          =---:...---:-===================---===++++++++++         
//          +----:...:-=======================--==+++++++++++        
//          +-:------====================++===---==++++===+++++      
//         +=-----======================+++++==---==+==-::=++**+     
//        +=-----================---=======++=========::.:-+*****    
//       +==::-====================--:  --:-====++=+===:..-=+*****   
//       +=---=====================-...  :=..:-=+++++++++===++*****  
//       +=---=====+=++++++++++++++++=-:::::-====+++++++++++++*****+ 
//      +=======++++++++++++=+++++++============++++++=======+****** 
//      +=====+++++++++++++++++++++++++==++++==++++++=:...  . .+**** 
//     ++====++++++++++++++++++++++++++++++++++++++++-.     ..-+**** 
//     +======++++++++++++++++++++++++++++++++===+====:.    ..:=++++ 
//     +===--=====+++++++++++++++++++++++++++=========-::....::-=++* 
//     ====--==========+++++++==+++===++++===========--:::....:=++*  
//     ====---===++++=====++++++==+++=======-::--===-:.  ....:-+++   
//     ==--=--====++++++++==+++++++++++======--::::...::::::-=+++    
//     ===----===++++++++++++++++++++============--=-==----==+++     
//     =--------====++++++++++++++++=====================+++++++     
//     =---------=======++++++++====+++=================++++++++     
//     -----------========+++++++++++++++=================+++++++    
//     =----------==========++++++++++=====================++++++++  
//     =====------==============+++++++===================+++==+++++ 
//     =======------==========================================++++++

	// created by : Nitesh Gupta

	public static void main(String[] args) throws Exception {

//		first();
//		sec();
//		third();
		four();
//			fif();
//			six();
	}

	private static void first() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] scn = (br.readLine()).trim().split(" ");
		int t = Integer.parseInt(scn[0]);
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			scn = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(scn[0]);
			long[] arr = new long[n];
			long[] brr = new long[n];
			for (int i = 0; i < n; i++) {
				scn = (br.readLine()).trim().split(" ");
				arr[i] = Long.parseLong(scn[0]);
				brr[i] = Long.parseLong(scn[1]);
			}

			long[] crr = new long[n];
			scn = (br.readLine()).trim().split(" ");
			for (int i = 0; i < n; i++) {
				crr[i] = Long.parseLong(scn[i]);
			}

			long[] xx = new long[n];
			xx[0] = arr[0];
			for (int i = 1; i < n; i++) {
				xx[i] = arr[i] - brr[i - 1];
			}
			int i = 0;
			long arrived = arr[i] + crr[i];

			long stay = (brr[i] - arr[i] + 1) / 2;
			arrived += stay;
			long depart = Math.max(brr[i], arrived);
			for (i = 1; i < n; i++) {
				arrived = depart + xx[i] + crr[i];
				stay = (brr[i] - arr[i] + 1) / 2;
				arrived += stay;
				depart = Math.max(brr[i], arrived);
			}

			sb.append(arrived - stay + "\n");
		}
		System.out.println(sb);
		return;
	}

	private static void sec() throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] scn = (br.readLine()).trim().split(" ");
		int t = Integer.parseInt(scn[0]);
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			scn = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(scn[0]);
			int[] arr = new int[n];
			scn = (br.readLine()).trim().split(" ");
			for (int i = 0; i < n; i++) {
				arr[i] = (int) Long.parseLong(scn[i]);
			}
			int[] ans = new int[n];
			int lay = 0;
			for (int i = n - 1; i >= 0; i--) {
				lay = Math.max(lay, arr[i]);
				if (lay >= 1) {
					ans[i] = 1;
					lay -= 1;
				}

			}
			for (int i : ans) {
				sb.append(i + " ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
		return;
	}

	private static void third() throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] scn = (br.readLine()).trim().split(" ");
		int n = Integer.parseInt(scn[0]);
		int[] arr = new int[n];
		scn = (br.readLine()).trim().split(" ");
		for (int i = 0; i < n; i++) {
			arr[i] = (int) Long.parseLong(scn[i]);
		}
		boolean found = false;
		HashMap<Integer, pair> map = new HashMap<Integer, pair>();
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				int sum = arr[i] + arr[j];
				if (!map.containsKey(sum)) {
					map.put(sum, new pair(i + 1, j + 1));
				} else {
					pair p = map.get(sum);
					HashSet<Integer> set = new HashSet<>();
					set.add(j + 1);
					set.add(i + 1);
					set.add(p.f);
					set.add(p.s);
					if (set.size() != 4)
						continue;
					System.out.println("YES");
					System.out.println(p.f + " " + p.s + " " + (i + 1) + " " + (j + 1));
					found = true;
					break;
				}
			}
			if (found)
				break;
		}
		if (!found) {
			System.out.println("NO");
		}
		return;
	}

	static class pair {
		int f, s;

		pair(int ff, int ss) {
			f = ff;
			s = ss;
		}

	};

	private static void four() throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] scn = (br.readLine()).trim().split(" ");
		int n = Integer.parseInt(scn[0]);
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			list.add(new ArrayList<>());
		}
		ArrayList<Integer> inp = new ArrayList<>();

		for (int i = 0; i < n-1; i++) {
			scn = (br.readLine()).trim().split(" ");
			int u = (int) Long.parseLong(scn[0]);
			int v = (int) Long.parseLong(scn[1]);
			list.get(v).add(u);
			list.get(u).add(v);
			inp.add(u);
			inp.add(v);

		}
		int max = 0;
		int idx = 0;

		for (int i = 1; i <= n; i++) {
			if (max < list.get(i).size()) {
				max = list.get(i).size();
				idx = i;
			}
		}
		int st = max;
		int an = 0;
		for (int i = 0; i < inp.size(); i += 2) {
			int u = inp.get(i);
			int v = inp.get(i + 1);
			if (u == idx || v == idx) {
				System.out.println(an++);
			} else {
				System.out.println(st++);
			}
		}

		return;

	}

	private static void fif() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] scn = (br.readLine()).trim().split(" ");
		int t = Integer.parseInt(scn[0]);
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			scn = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(scn[0]);
			long[] arr = new long[n];
			scn = (br.readLine()).trim().split(" ");
			for (int i = 0; i < n; i++) {
				arr[i] = Long.parseLong(scn[i]);
			}

			sb.append("\n");
		}
		System.out.println(sb);
		return;
	}

	private static void six() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] scn = (br.readLine()).trim().split(" ");
		int t = Integer.parseInt(scn[0]);
		StringBuilder sb = new StringBuilder();

		while (t-- > 0) {
			scn = (br.readLine()).trim().split(" ");
			int n = Integer.parseInt(scn[0]);
			long[] arr = new long[n];
			scn = (br.readLine()).trim().split(" ");
			for (int i = 0; i < n; i++) {
				arr[i] = Long.parseLong(scn[i]);
			}

			sb.append("\n");
		}
		System.out.println(sb);
		return;
	}

	public static void sort(long[] arr) {
		int n = arr.length;
		for (int i = 0; i < n; i++) {
			int idx = (int) Math.random() * n;
			long temp = arr[i];
			arr[i] = arr[idx];
			arr[idx] = temp;
		}
		Arrays.sort(arr);
	}

	public static void print(long[][] dp) {
		for (long[] a : dp) {
			for (long ele : a) {
				System.out.print(ele + " ");
			}
			System.out.println();
		}
	}

}