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 cp;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {

    static long dist[][];
    static long mod=1000000000+7;
    static SegmentTree st;
    static int n;
    static HashSet<Long> set;
    static long fen[];
    static int x;
    static double arr[];
    static double arr2[];
    static long comb[];
    static long inverse[];
    static int blockSize;
    static int blockCount;
    static int d;
    static int k;
    static int pxor[];
    static ArrayList<ArrayList<pair>> llist;
    static ArrayList<HashMap<Integer,Integer>> lofmap;
    static int fenLen=1000000+100;
    static long dp[][];
    static long count[];
    static ArrayList<ArrayList<Integer>> listList;
	public static void main(String[] args) {
        SReader sc=new SReader();
        n=sc.ni();
        llist=new ArrayList<>();
        count=new long[n-1];
        for(int i=0;i<n;i++)
        {
        	llist.add(new ArrayList<>());
        }
        for(int i=0;i<n-1;i++)
        {
        	
        	int u=sc.ni()-1;
        	int v=sc.ni()-1;
        	
        	llist.get(u).add(new pair(v,i));
        	llist.get(v).add(new pair(u,i));
        	
        }
        dfs(0,-1);
        ArrayList<pair> list=new ArrayList<>();
        for(int i=0;i<count.length;i++)
        {
        	list.add(new pair(count[i],i));
        }
        Collections.sort(list,new cust());
        int ans[]=new int[n-1];
        
        //System.out.println(list);
        
        for(int i=0;i<n-1;i++)
        {
        	ans[(int)list.get(i).b]=i;
        	
        }
        
        for(int i=0;i<n-1;i++)
        {
        	System.out.println(ans[i]);
        }
        
        
	}
	
	public  static class cust implements Comparator<pair>
	{
		public int compare(pair p1,pair p2)
		{
			if(p1.a!=p2.a)
			{
				return Long.compare(p1.a,p2.a);
			}
			return Long.compare(p1.b,p2.b);
		}
	}
	
	public static long dfs(int node,int parent)
	{
		long below=1;
		ArrayList<pair> list=llist.get(node);
		for(int i=0;i<list.size();i++)
		{
			if(list.get(i).a!=parent)
			{
				long b=dfs((int)list.get(i).a,node);
				count[(int)list.get(i).b]=(b)*(long)(n-b);
				below+=b;
			}
		}
		return below;
	}
	
	public static class pa
	{
		double a;
		double b;
		pa(double a,double b)
		{
			this.a=a;this.b=b;
		}
	}
	
	static TreeSet<String> map;
	public static void recurse(int r,int c,int steps,int prev)
	{
		if(steps==n)
		{
			if(!map.contains(r+" "+c))
			{
				map.add((r+" "+c));
				//System.out.println(r+" "+c);
			}
			return ;
		}
		if(prev==0)
		{
			recurse(r+1,c,steps+1,1);
			recurse(r-1,c,steps+1,1);
		}
		else
		{
			recurse(r,c+1,steps+1,0);
			recurse(r,c-1,steps+1,0);
		}
	}
	
	public static boolean valid(int x,int y) {
		return x>-1&&y>-1&&x<n&&y<n;
	}
	public static class ob
	{
		int x;int y;
		int prev;
		ob(int x,int y,int prev)
		{
			this.x=x;
			this.y=y;
		}
	}
	
	
	public static long nCr(int n,int r)
	{
		if(r==0)
			return 1;
		
		if(r>n)
			return 0;
		
		long denominator=(inverse[r]*inverse[n-r])%mod;
		long dinverse=denominator;
		return (comb[n]*dinverse)%mod;	
	}
	
	static long modInverse(long a) 
    { 
		long m=mod;
        long g = gcd(a, m); 
        return power(a, m - 2, m); 
    } 
  
    static long power(long x, long y, long m) 
    { 
        if (y == 0) 
            return 1; 
  
        long p = power(x, y / 2, m) % m; 
        p = (p * p) % m; 
  
        if (y % 2 == 0) 
            return p; 
        else
            return (x * p) % m; 
    } 
  
    static long gcd(long a, long b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    } 
	
	public static long getInRange(int p1,int p2)
	{
		return get(p2)-get(p1-1);
	}
	
	public static void add(int pos,long diff)
	{
		pos+=1;
		while(pos<fenLen)
		{
			fen[pos]+=diff;
			pos+=(pos&(-pos));
		}
	}
	
	public static long get(int pos)
	{
		pos+=1;
		long ans=0;
		while(pos>0)
		{
			ans+=fen[pos];
			pos-=pos&(-pos);
		}
		return ans;
	}
	
	static class pair
	{
		long a;
		long b;
		pair(long a,long b)
		{
			this.a=a;
			this.b=b;
		}
		
		
		public String toString()
		{
			return a+" "+b;
		}
	}
    
    static final int MAXN = 100001;
 
    static Vector<Integer>[] tree = new Vector[MAXN];
    static int[][] path = new int[3][MAXN]; 
    static boolean flag;
 
    static void dfs(int cur, int prev, int pathNumber, int ptr, int node) 
    {
        for (int i = 0; i < tree[cur].size(); i++) 
        {
            if (tree[cur].get(i) != prev && !flag)
            {
                path[pathNumber][ptr] = tree[cur].get(i);
                if (tree[cur].get(i) == node) 
                {
                    flag = true;
 
                    path[pathNumber][ptr + 1] = -1;
                    return;
                }
                dfs(tree[cur].get(i), cur, pathNumber, ptr + 1, node);
            }
        }
    }
    static int lca(int a, int b) 
    {
        if (a == b)
            return a;
 
        path[1][0] = path[2][0] = 1;
 
        flag = false;
        dfs(1, 0, 1, 1, a);
 
        flag = false;
        dfs(1, 0, 2, 1, b);
 
        int i = 0;
        while (i < MAXN && path[1][i] == path[2][i])
            i++;
 
        return path[1][i - 1];
    }
 
    static void addEdge(int a, int b) 
    {
        tree[a].add(b);
        tree[b].add(a);
    }
    
    public static long getDist(int pos,int dest,int parent)
    {
        if(pos==dest)
            return 0;
        ArrayList<Integer> list=listList.get(pos);
        long dist=Integer.MAX_VALUE;
        for(int i:list)
        {
            if(i!=parent)
            {
                dist=Math.min(dist,1+getDist(i,dest,pos));
            }
        }
        return dist;
    }
    
    
    
    
    
    
    static class SegmentTree
    {
        static int MAX =10000000;
        //Trees For Max query
    static double tree[] = new double[MAX];
    static double lazy[] = new double[MAX];
    //Trees for Min query
    static double tree2[] =new double[MAX];
    static double lazy2[] = new double[MAX];

    static void updateRangeUtil(int si, int ss, int se, int us,
                                int ue, double diff)
    {
        if (lazy[si] != 0)
        {
            tree[si] += lazy[si];
            if (ss != se)
            {
                lazy[si * 2 + 1] += lazy[si];
                lazy[si * 2 + 2] += lazy[si];
            }
            lazy[si] = 0;
        }
        if (ss > se || ss > ue || se < us)
            return;

        if (ss >= us && se <= ue)
        {
            tree[si] += diff;
            if (ss != se)
            {
                lazy[si * 2 + 1] += diff;
                lazy[si * 2 + 2] += diff;
            }
            return;
        }
        int mid = (ss + se) / 2;
        updateRangeUtil(si * 2 + 1, ss, mid, us, ue, diff);
        updateRangeUtil(si * 2 + 2, mid + 1, se, us, ue, diff);
        tree[si] = Math.max(tree[si * 2 + 1], tree[si * 2 + 2]);
    }
    static void updateRange(int n, int us, int ue, double diff)
    {
        updateRangeUtil(0, 0, n - 1, us, ue, diff);
    }
    static double getMaxUtil(int ss, int se, int qs, int qe, int si)
    {
        if (lazy[si] != 0)
        {
            tree[si] += lazy[si];
            if (ss != se)
            {
                lazy[si * 2 + 1] += lazy[si];
                lazy[si * 2 + 2] += lazy[si];
            }
            lazy[si] = 0;
        }
        if (ss > se || ss > qe || se < qs)
            return Long.MIN_VALUE;
        if (ss >= qs && se <= qe)
        {
        	if(tree[si]==0)
        	{
        		return 1;
        	}
            return tree[si];
        }
        int mid = (ss + se) / 2;
        return (getMaxUtil(ss, mid, qs, qe, 2 * si + 1)*
                getMaxUtil(mid + 1, se, qs, qe, 2 * si + 2));
    }
    static double getMax(int n, int qs, int qe)
    {
        return getMaxUtil(0, n - 1, qs, qe, 0);
    }
    static void constructSTUtil(double arr[], int ss, int se, int si)
    {
        if (ss > se)
            return;
        if (ss == se)
        {
            tree[si] = arr[ss];
            return;
        }
        int mid = (ss + se) / 2;
        constructSTUtil(arr, ss, mid, si * 2 + 1);
        constructSTUtil(arr, mid + 1, se, si * 2 + 2);
        tree[si] =(tree[si * 2 + 1]*tree[si * 2 + 2]);
    }
    static void constructSTUtil2(long arr[], int ss, int se, int si)
    {
        if (ss > se)
            return;
        if (ss == se)
        {
            tree2[si] = arr[ss];
            return;
        }
        int mid = (ss + se) / 2;
        constructSTUtil2(arr, ss, mid, si * 2 + 1);
        constructSTUtil2(arr, mid + 1, se, si * 2 + 2);
        tree2[si] = Math.min(tree2[si * 2 + 1], tree2[si * 2 + 2]);
    }

    static void constructST(double arr[], int n)
    {
        constructSTUtil(arr, 0, n - 1, 0);
    }
    }
    
    
    static class SReader {
        BufferedReader br;
        StringTokenizer st;

        public SReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        public static void pr(Object s) {
            System.out.println(s);
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int ni() {
            return Integer.parseInt(next());
        }

        long nl() {
            return Long.parseLong(next());
        }

        double nd() {
            return Double.parseDouble(next());
        }

        String rl() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}