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.io.*;
import java.util.*;
public class MyClass {
    
    public static void main(String args[]) {
      FastReader sc = new FastReader();     //For Fast IO
      int n = sc.nextInt();
      ArrayList<Integer> adj[] = new ArrayList[n+1];
      int ans[] = new int[n+1];
      Arrays.fill(ans,-1);
      for(int i=1;i<=n;i++){
          adj[i]=new ArrayList<>();
      }
      for(int i=1;i<n;i++){
          int x = sc.nextInt();
          int y = sc.nextInt();
          adj[x].add(i);
          adj[y].add(i);
      }
      Pair max = new Pair(0,0);
      for(int i=1;i<=n;i++){
          int size = adj[i].size();
          int node = i;
          if(max.x<size && max.y<node){
              max = new Pair(size,node);
          }
      }
      int curr=0;
      for(Integer edgeno : adj[max.y]){
          ans[edgeno] = curr++;
      }
      for(int i=1;i<n;i++){
          if(ans[i]==-1){
              ans[i]=curr++;
          }
          System.out.println(ans[i]);
      }
    }
}
class Pair{
    int x;
    int y;
    Pair(int i,int j){
        x=i;
        y=j;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Pair)) return false;
        Pair key = (Pair) o;
        return x == key.x && y == key.y;
    }
    @Override
    public int hashCode() {
        int result = x;
        result = 31*result + y;
        return result;
    }
}
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; 
		} 
	}