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:
//package codeforces;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.*;
import java.util.ArrayList;
public final class Codeforces {
             static int p=1000000000,ans[],parity,s,e;
          static ArrayList<edge>g;
          static HashMap<Integer,ArrayList<edge>>map;
    public static void main(String[] args) throws Exception{
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);        
        FastReader sc = new FastReader();
      int n,u,v;
      n=sc.nextInt();
      ans=new int[n-1];
      map=new HashMap<>();
     g=new ArrayList<>();
            pair po[]=new pair[n-1];
      for(int i=0;i<n-1;i++)
      {
        u=sc.nextInt();
        v=sc.nextInt();
        add_edge(u,v,i);         
      }
      s=0;
     
      for(Integer p:map.keySet())
      {
         if(map.get(p).size()>=3)
         {
             ArrayList<edge>list=map.get(p);
             list.get(0).weight=s++;
             list.get(1).weight=s++;
             list.get(2).weight=s++;
             break;
         }
      }
      for(edge ee:g)
      {
          if(ee.weight==-1)ee.weight=s++;
      }
      for(edge ee:g)out.write(ee.weight+" "+'\n');
              out.write('\n');
         out.flush();
    }
  
    static class pair
    {
        int i,v,weight=-1;
        pair(int v,int i)
        {
            this.v=v;
            this.i=i;
        }
    }
    
    static class edge{
        int u,v,id,weight=-1;
        edge(int u,int v,int id)
        {
            this.u=u;this.v=v;this.id=id;
        }
    }
    
    public static void add_edge(int u,int v,int id)
    {
        edge e=new edge(u,v,id);
        g.add(e);
        if(map.containsKey(u))
        {
            ArrayList<edge>list=map.get(u);
            list.add(e);
            map.put(u,list);
        }
        else
        {
            ArrayList<edge>list=new ArrayList<>();
            list.add(e);
            map.put(u, list);
        }
              if(map.containsKey(v))
        {
            ArrayList<edge>list=map.get(v);
            list.add(e);
            map.put(v,list);
        }
        else
        {
            ArrayList<edge>list=new ArrayList<>();
            list.add(e);
            map.put(v, list);
        }
        
    }
    

   
    static class FastReader {        

        BufferedReader br;        
        StringTokenizer st;        
        
        public FastReader() {            
            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;            
        }        
    }   
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////// 
}