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


public class Forces{

    public static PrintWriter cout;
    public static void main(String ...arg) throws IOException
    {
        //Read cin = new Read();
        InputReader cin = new InputReader(System.in);
        //Scan cin =new Scan();
        cout = new PrintWriter(new BufferedOutputStream(System.out));
        int n = cin.nextInt();
        ArrayList<Integer>[] adj = new ArrayList[n];
        for(int i=0;i<n;i++)
        	adj[i] = new ArrayList<Integer>();
        int[] ans = new int[n];
        Arrays.fill(ans,-1);
        //i is for the edge label
        //a and b are the nodes
        for(int i=1;i<n;i++)
        {
        	int a = cin.nextInt()-1;
        	int b = cin.nextInt()-1;
        	adj[a].add(i);
        	adj[b].add(i);
        }
        //cout.print(Arrays.deepToString(adj));
        int label = 0;
        for(int i=0;i<n;i++)
        {
        	if(adj[i].size()>=3)
        	{
        		ans[adj[i].get(0)] = 0;
        		ans[adj[i].get(1)] = 1;
        		ans[adj[i].get(2)] = 2;
        		label = 3;
        		break;
        	}
        }
        for(int i=1;i<n;i++)
        {
        	if(ans[i] == -1)
        	{
        		ans[i] = label;
        		label++;
        	}
        }
        for(int i=1;i<n;i++)
        	cout.println(ans[i]);

        cout.close();
     }



     static class InputReader {
        final InputStream is;
        final byte[] buf = new byte[1024];
        int pos;
        int size;
 
        public InputReader(InputStream is) {
            this.is = is;
        }
 
        public int nextInt() {
            int c = read();
            while (isWhitespace(c))
                c = read();
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = res * 10 + c - '0';
                c = read();
            } while (!isWhitespace(c));
            return res * sign;
        }
 
        int read() {
            if (size == -1)
                throw new InputMismatchException();
            if (pos >= size) {
                pos = 0;
                try {
                    size = is.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (size <= 0)
                    return -1;
            }
            return buf[pos++] & 255;
        }
 
        static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
    }




static class Scan {
        private byte[] buf=new byte[1024];
        private int index;
        private InputStream in;
        private int total;
        public Scan()
        {
            in=System.in;
        }
        public int scan()throws IOException
        {
            if(total<0)
            throw new InputMismatchException();
            if(index>=total)
            {
                index=0;
                total=in.read(buf);
                if(total<=0)
                return -1;
            }
            return buf[index++];
        }
        public int scanInt()throws IOException
        {
            int integer=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n))
            {
                if(n>='0'&&n<='9')
                {
                    integer*=10;
                    integer+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            return neg*integer;
        }
        public double scanDouble()throws IOException
        {
            double doub=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n)&&n!='.')
            {
                if(n>='0'&&n<='9')
                {
                    doub*=10;
                    doub+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            if(n=='.')
            {
                n=scan();
                double temp=1;
                while(!isWhiteSpace(n))
                {
                    if(n>='0'&&n<='9')
                    {
                        temp/=10;
                        doub+=(n-'0')*temp;
                        n=scan();
                    }
                    else throw new InputMismatchException();
                }
            }
            return doub*neg;
        }
        public String scanString()throws IOException
        {
            StringBuilder sb=new StringBuilder();
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            while(!isWhiteSpace(n))
            {
                sb.append((char)n);
                n=scan();
            }
            return sb.toString();
        }
        private boolean isWhiteSpace(int n)
        {
            if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
            return true;
            return false;
        }
    }

}

class Read
{
    private BufferedReader br;
    private StringTokenizer st;

    public Read()
    { br = new BufferedReader(new InputStreamReader(System.in)); }

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

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

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

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

    String nextLine()
    {
        String str = "";
        try {str = br.readLine();}
        catch(IOException e)
            {e.printStackTrace();}
        return str;
    }
}