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:

// Problem: C. Ehab and Path-etic MEXs
// Contest: Codeforces - Codeforces Round #628 (Div. 2)
// URL: http://codeforces.com/contest/1325/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

import java.io.*;
import java.util.*;

public class Main {
    private static PrintWriter pw = new PrintWriter(System.out);
    private static InputReader sc = new InputReader();
    private static final int intmax = Integer.MAX_VALUE, intmin = Integer.MIN_VALUE;

    static class Pair{
        int first;
        int second;
        Pair(int first, int second){
            this.first = first;
            this.second = second;
        }
    }

    static class InputReader{
        private static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        private static StringTokenizer tk;

        private void next()throws IOException{
            if(tk == null || !tk.hasMoreTokens())   
                tk = new StringTokenizer(r.readLine());
        }

        private int nextInt()throws IOException{
            next();
            return Integer.parseInt(tk.nextToken());
        }

        private long nextLong()throws IOException{
            next();
            return Long.parseLong(tk.nextToken());
        }

        private String readString()throws IOException{
            next();
            return tk.nextToken();
        }

        private double nextDouble()throws IOException{
            next();
            return Double.parseDouble(tk.nextToken());
        }

        private int[] intArray(int n)throws IOException{
            next();
            int arr[] = new int[n];

            for(int i=0; i<n; i++)
                arr[i] = nextInt();

            return arr;
        }

        private long[] longArray(int n)throws IOException{
            next();
            long arr[] = new long[n];

            for(int i=0; i<n; i++)
                arr[i] = nextLong();

            return arr;
        }
    }

    public static void main(String args[])throws IOException{
        int t = 1;
        while(t-->0)    solve();
        pw.flush();
        pw.close();
    }

    private static void solve()throws IOException{
		int n = sc.nextInt();
		
		ArrayList<ArrayList<Pair>> tree = new ArrayList<>();
		
		for(int i=0; i<n; i++)	tree.add(new ArrayList<>());
		
		int res[] = new int[n-1];
		
		for(int i=0; i<n-1; i++){
			res[i] = -1;
			int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
			tree.get(u).add(new Pair(v, i));
			tree.get(v).add(new Pair(u, i));
		}
		
		boolean w = false;
		for(int i=0; i<n; i++){
			if(tree.get(i).size() > 2){
				for(int t=0; t<3; t++){
					int j = tree.get(i).get(t).first, ind = tree.get(i).get(t).second;
					res[ind] = t;
				}
				w = true;
				break;
			}
		}
		
		int q = w ? 3 : 0;
		
		for(int i=0; i<n; i++){
			for(Pair p : tree.get(i)){
				int j = p.first, ind = p.second;
				if(res[ind] == -1)
					res[ind] = q++;
			}
		}
		
		for(int p: res)	pw.println(+p);
    }
}