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

public class Main
{   
    static class Edge{
        int a,b,label;
        public Edge(int a,int b){
            this.a=a;
            this.b=b;
            label=-1;
        }
    }

    static class Graph{
        int V,deg[],cnt=0;
        ArrayList<Edge> l[];
        //TreeSet<Integer> set=new TreeSet<Integer>();
        ArrayList<Edge> li = new ArrayList<>();
        public Graph(int v){
            V=v;
            deg=new int[V+1];
            l=new ArrayList[V+1];

            for(int i=1;i<=V;i++){
                l[i]=new ArrayList<Edge>(); 
                //set.add(i);
            }
        }

        void addEdge(int u,int v){
            Edge ed=new Edge(u,v);
            l[u].add(ed);
            l[v].add(ed);

            li.add(ed);

            deg[u]++;
            deg[v]++;
        }

        void do_stuff(){
            for(int i=1;i<=V;i++){
                if(deg[i]<3)
                    continue;

                for(int j=1;j<=3;j++){
                    Edge e=l[i].get(j-1);
                    e.label=cnt++;
                }
                break;
            }
            //System.out.println("dfas");
            for(Edge e : li){
                //System.out.println(e.label);
                if(e.label!=-1){
                    pn(e.label);
                    continue;
                }

                pn(cnt++);
            }
        }
    }
    public static void process()throws IOException
    {
        int n=ni();
        Graph g=new Graph(n);

        for(int i=1;i<n;i++)
            g.addEdge(ni(),ni());
       // System.out.println("ds");
        g.do_stuff();
    }


   	static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        out = new PrintWriter(System.out);
        sc=new AnotherReader();
        boolean oj = true;

    	oj = System.getProperty("ONLINE_JUDGE") != null;
    	if(!oj) sc=new AnotherReader(100);

        long s = System.currentTimeMillis();
        int t=1;
        while(t-->0)
            process();
        out.flush();
        if(!oj)
            System.out.println(System.currentTimeMillis()-s+"ms");
        System.out.close();  
    }

    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);System.out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
    static boolean multipleTC=false;



/////////////////////////////////////////////////////////////////////////////////////////////////////////

    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
    
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
	
	
	