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.lang.*;
import java.io.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class ProblemC {
	
	public static class Edge {
		int u, v;
		
		Edge(int u, int v) {
			this.u = u;
			this.v = v;
		}
	}
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
 
		FastReader s = new FastReader();
		int n = s.nextInt();
		
		Edge[] edge = new Edge[n+1];
		ArrayList<Integer>[] node = new ArrayList[n+1];
		
		for(int i=1;i<=n;i++) {
			node[i] = new ArrayList<>();
		}
		for(int i=0;i<n-1;i++) {
			int u = s.nextInt();
			int v = s.nextInt();
			
			edge[i] = new Edge(u, v);
			node[u].add(i);
			node[v].add(i);
		}
		
		if(n==2) {
			System.out.println(0);
		}
		
		else if(n==3) {
			System.out.println(0);
			System.out.println(1);
		}
		
		else {
			int leaf1 = -1, leaf2 = -1;
			
			for(int i=1;i<=n;i++) {
				if(node[i].size()==1) {
					if(leaf1 == -1)
						leaf1 = i;
					else if(leaf2 == -1) {
						leaf2 = i;
						break;
					}
				}
			}
			
			if(leaf2 == -1) {
				for(int i=0;i<n-1;i++) {
					System.out.println(i);
				}
			} 
			else {
				int[] ans = new int[n];
				
				int ed1 = node[leaf1].get(0);
				int ed2 = node[leaf2].get(0);
				ans[ed1] = 0;
				ans[ed2] = 1;
				
				boolean[] cov_edge = new boolean[n-1];
				
				dfs(leaf1, leaf2, cov_edge, edge, node, -1);
				
				boolean twoFound = false;
				for(int i=0;i<n-1;i++) {
					if(!cov_edge[i])
					{
						ans[i] = 2;
						twoFound = true;
						break;
					}
				}
				
				int count = 3;
				
				if(!twoFound)
					count = 2;
				for(int i=0;i<n-1;i++) {
					if(i == ed1 || i== ed2 || ans[i] !=0)
						continue;
					else {
						ans[i] = count++;
					}
				}
				
				for(int i=0;i<n-1;i++)
					System.out.println(ans[i]);
			}
		}
	}
	
	public static boolean dfs(int nd, int target, boolean[] cov_edge, Edge[] edge,ArrayList<Integer>[] node, int src) {
		if(nd == target)
			return true;
		
		else {
			ArrayList<Integer> adj = node[nd];
			
			for(int i=0;i<adj.size();i++) {
				int to = 0;
				Edge e = edge[adj.get(i)];
				if(e.u==nd)
					to = e.v;
				else
					to = e.u;
				
				if(to == src)
					continue;
				boolean found = dfs(to, target, cov_edge, edge, node, nd);
				
				if(found) {
					cov_edge[adj.get(i)] = true;
					return true;
				}
			}
			
			return false;
		}
	}
	
	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;
        }
    }
 
}