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 static java.lang.Double.max;
import static java.lang.Integer.min;
import static java.lang.Math.pow;
import static java.util.Collections.sort;
public class Main {
    static long mod=998244353;
    static HashMap<Long,Integer> M=new HashMap();
    static boolean B[]=new boolean[100001];
    static FastReader in=new FastReader();
    static List<Integer >G[];
    public static void main(String [] args) {
        int t=1;
        StringBuilder Sd=new StringBuilder(); 
                
        while(t-->0){
            int n=in.nextInt();
            ArrayList <Integer>A=new ArrayList(),B=new ArrayList();
            G=new List[n+1];
            int x[]=new int[n+1];
            for(int i=0;i<=n;i++)G[i]=new ArrayList();
        for(int i=0;i<n-1;i++){A.add(in.nextInt());B.add(in.nextInt());
        G[A.get(i)].add(B.get(i));
        G[B.get(i)].add(A.get(i));
        x[A.get(i)]++;x[B.get(i)]++;
        }
        int ans[]=new int[n-1],min=0,max=n-2;
        for(int i=0;i<n-1;i++){
        if(x[A.get(i)]==1||x[B.get(i)]==1){ans[i]=min;min++;}
        else {ans[i]=max;max--;}
        }
        for(int i=0;i<n-1;i++){
        Sd.append(ans[i]);
        
        Sd.append("\n");
        }
        }
        System.out.print(Sd);
    }
    
   static void Dfs(int o,int max,int min,boolean p){
   B[o]=true;
  for(int i:G[o]){
      if(!B[i]){
  if(p){
      long h=(long)i,j=(long)o;
      h*=1000000;
      h+=j;
      M.put(h, min);
      min++;Dfs(i,max,min,!p);}
  else{
      long h=(long)i,j=(long)o;
      h*=1000000;
      h+=j;
      M.put(h, max);
      max--;Dfs(i,max,min,p);}
      }
  }
   }
    static long gcd(long g,long x){
        if(x<1)return g;
        else return gcd(x,g%x);
    
    }
}
class node implements Comparable<node>{
int f, e;
node(int tt,int ll){
f=tt;e=ll;
}
    @Override
    public int compareTo(node o) {
    return f-o.f;    
    }
}
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;
        }
}
 
class Sorting{
 
 public static int[] bucketSort(int[] array, int bucketCount) {
 
 if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
 
 if (array.length <= 1) return array; //trivially sorted
 
 
 
 int high = array[0];
 
 int low = array[0];
 
 for (int i = 1; i < array.length; i++) { //find the range of input elements
 
 if (array[i] > high) high = array[i];
 
 if (array[i] < low) low = array[i];
 
 }
 
 double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
 
 
 ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
 
 for (int i = 0; i < bucketCount; i++) { //initialize buckets
 
 buckets[i] = new ArrayList();
 
 }
 
 
 
 for (int i = 0; i < array.length; i++) { //partition the input array
 
 buckets[(int)((array[i] - low)/interval)].add(array[i]);
 
 }
 
 
 int pointer = 0;
 
 for (int i = 0; i < buckets.length; i++) {
 
 Collections.sort(buckets[i]); //mergeSort
 
 for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
 
 array[pointer] = buckets[i].get(j);
 
 pointer++;
 
 }
 
}
 
return array;
 
}
 
}