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

public class Solution {
    private static final long mod = 1000000007;
    static int curlVal = 0;

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

        FastScanner sc = new FastScanner();
        PrintWriter out=new PrintWriter(System.out);
        int t;
        t = 1;//sc.nextInt();

        while (t-- > 0) {
            solve(sc,out);
        }
        out.close();

    }

    public static void solve(FastScanner sc, PrintWriter out) {
        int n = sc.nextInt();
        ArrayList<Integer> al[] = adjacencyList(n);
        int pairs[][] = new int[n-1][2];
        getEdgesCustom(al,n-1,sc,pairs);
        int values[] = new int[n+1];
        int start = 0;
        Arrays.fill(values,-1);
        dfsTreeCutsom(al,1,0,values);
        if(n > 2)
        for(int i = 0;i<n-1;i++){
            int x = pairs[i][0];
            int y = pairs[i][1];
            if(values[x] != -1){
                out.println(values[x]);
            } else if(values[y] != -1)
                out.println(values[y]);
            else out.println(curlVal++);
        } else
            out.println(0);
        out.println(); out.flush();
    }

    public static void dfsTreeCutsom(ArrayList<Integer> al[], int node, int parent, int values[]){
        for(int child : al[node]){
            if(child != parent)
                dfsTreeCutsom(al, child, node, values);
        }
        if(al[node].size() == 1){
            values[node] = curlVal;
            curlVal++;
        }
    }

    public static void getEdgesCustom(ArrayList<Integer> al[], int size, FastScanner sc, int[][] pair){
        for(int i = 0;i<size;i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            pair[i][0] = x;
            pair[i][1] = y;
            al[x].add(y);
            al[y].add(x);
        }
    }

    public static void getEdges(ArrayList<Integer> al[], int size, FastScanner sc){
        for(int i = 0;i<size;i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            al[x].add(y);
            al[y].add(x);
        }
    }

    public static ArrayList<Integer>[] adjacencyList(int size){
        ArrayList<Integer> al[] = new ArrayList[size+1];
        for(int i = 1; i<=size;i++)
            al[i] = new ArrayList<>();
        return al;
    }

    public static void dfsTree(ArrayList<Integer> al[], int node, int parent){
        for(int child : al[node]){
            if(child != parent)
                dfsTree(al, child, node);
        }
        if(al[node].size() == 1 && al[node].get(0) == parent){
            //
        }
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        public String next() {
            while (!st.hasMoreElements())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

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

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

        public int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

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

    }
}