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.IOException;
import java.io.InputStream;
import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;


public class Solution {
    static int n;
    static ArrayList<Integer> tree[];
    public static void main(String[] args) throws IOException {
        FastReader in = new FastReader(System.in);
        StringBuilder sb = new StringBuilder();
        int i,j;
        n=in.nextInt();
        tree=new ArrayList[n];
        ArrayList<Integer> list[]=new ArrayList[n];
        for(i=0;i<n;i++) {
            tree[i] = new ArrayList<>();
            list[i]=new ArrayList<>();
        }
        for(i=0;i<n-1;i++){
            int x=in.nextInt()-1;
            int y=in.nextInt()-1;
            tree[x].add(y);
            tree[y].add(x);
            list[x].add(i);
            list[y].add(i);
        }
        int f=0;
        int ans[]=new int[n-1];
        HashSet<Integer> set=new HashSet<>();
        for(i=0;i<n;i++){
            if(tree[i].size()>2){
                f=1;
                ans[list[i].get(0)]=0;
                ans[list[i].get(1)]=1;
                ans[list[i].get(2)]=2;
                set.add(list[i].get(0));
                set.add(list[i].get(1));
                set.add(list[i].get(2));
                break;

            }
        }
        if(f==0){
            for(i=0;i<n-1;i++)
                sb.append(i).append("\n");
        }
        else{
            int k=3;
            for(i=0;i<n-1;i++){
                if(!set.contains(i))
                    ans[i]=k++;
                sb.append(ans[i]).append("\n");
            }
        }

        System.out.print(sb);

    }
}
class FastReader {

    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;

    FastReader(InputStream is) {
        in = is;
    }

    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }

    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }

    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}