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.io.*;
     
    public class Solution
    {
        public static void main(String args[])throws IOException
        {
            FastReader in=new FastReader(System.in);
            int i,j;
            int fg=0;
            
            //long min=Long.MAX_VALUE;
            //long max=Long.MIN_VALUE;
            
            //int t=in.nextInt();
            int t=1;
            for(i=0;i<t;i++)
            {
                int n=in.nextInt();
                Integer EdgecountOfNodes[]=new Integer[n+1];
                Integer answer[]=new Integer[n];
                for(i=0;i<n-1;i++)
                {
                    answer[i]=n+1;
                    EdgecountOfNodes[i]=0;
                }
                EdgecountOfNodes[n-1]=0;
                EdgecountOfNodes[n]=0;
                ArrayList<Integer> el=new ArrayList<>();
                ArrayList<Integer> er=new ArrayList<>();
                for(i=0;i<n-1;i++)
                {
                    int n1=in.nextInt();
                    int n2=in.nextInt();
                    EdgecountOfNodes[n1]++;
                    EdgecountOfNodes[n2]++;
                    el.add(n1);
                    er.add(n2);
                }
                for(i=1;i<n-1;i++)
                {
                    if(EdgecountOfNodes[el.get(i)]==1 || EdgecountOfNodes[er.get(i)]==1)
                    {
                        answer[i]=fg;
                        fg++;
                    }
                }
                for(j=0;j<n-1;j++)
                {
                    if(answer[j]==n+1)
                    {
                        answer[j]=fg;
                        fg++;
                    }
                }
                for(j=0;j<n-1;j++)
                {
                    System.out.println(answer[j]);
                }
            }
            return;
        }
    }
    class A
    {
        int a;
        int b;
        public A(int a,int b)
        {
            this.a=a;
            this.b=b;
        }
    }
     
    class FastReader
    { 
        byte[] buf = new byte[2048];
        int index, total;
        InputStream in;
     
        FastReader(InputStream is) {
            in = is;
        }
     
        int scan() throws IOException {
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0) {
                    return -1;
                }
            }
            return buf[index++];
        }
     
        String next() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan()) ;
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }
     
        String nextLine() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan()) ;
            StringBuilder sb = new StringBuilder();
            for (; c != 10 && c != 13; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }
     
        char nextChar() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan()) ;
            return (char) c;
        }
     
        int nextInt() throws IOException {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
     
        long nextLong() throws IOException {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
    }