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>
import java.util.*;
import java.io.*;

public class EhabAndPatheticMEXs {
	public static void main(String[] args) throws IOException{
        Scan S = new Scan();
        Print P = new Print();

        int N, u, v;
        N = S.scanInt();

        List<List<Integer>> graph = new ArrayList<>(Collections.nCopies(N+1, null));
        List<Integer> labels = new ArrayList<>(Collections.nCopies(N-1, 0));

        for(int i=0; i<N-1; i++){
            u = S.scanInt();
            v = S.scanInt();

            if(Objects.isNull(graph.get(u))){
                graph.set(u, new ArrayList<>());
            }
            if(Objects.isNull(graph.get(v))){
                graph.set(v, new ArrayList<>());
            }

            graph.get(u).add(i);
            graph.get(v).add(i);

            labels.set(i, -1);    
        }

        int max_size = 0, max_node = 0;
        for(int i=1; i<=N; i++){
            if(graph.get(i).size()>max_size){
                max_size = graph.get(i).size();
                max_node = i;
            }
        }

        int counter = 0;
        for(Integer i : graph.get(max_node)){
            labels.set(i.intValue(), counter);
            counter++;
        }

        for(int i=0; i<N-1; i++){
            if(labels.get(i)==-1){
                labels.set(i, counter);
                counter++;
            }
        }

        for(Integer i: labels)
            P.println(i);

        P.close();
    }
}

class Print {
    private final BufferedWriter bw;
    public Print() {
        this.bw=new BufferedWriter(new OutputStreamWriter(System.out));
    }
    public void print(Object object)throws IOException {
        bw.append(""+object);
    }
    public void println(Object object)throws IOException {
        print(object);
        bw.append("\n");
    }
    public void close()throws IOException {
        bw.close();
    }
}
class Scan {
    private byte[] buf=new byte[1024];
    private int index;
    private InputStream in;
    private int total;
    public Scan() {
        in=System.in;
    }
    public int scan()throws IOException {
        if(total<0)
        throw new InputMismatchException();
        if(index>=total)
        {
            index=0;
            total=in.read(buf);
            if(total<=0)
            return -1;
        }
        return buf[index++];
    }
    public int scanInt()throws IOException {
        int integer=0;
        int n=scan();
        while(isWhiteSpace(n))
        n=scan();
        int neg=1;
        if(n=='-')
        {
            neg=-1;
            n=scan();
        }
        while(!isWhiteSpace(n))
        {
            if(n>='0'&&n<='9')
            {
                integer*=10;
                integer+=n-'0';
                n=scan();
            }
            else throw new InputMismatchException();
        }
        return neg*integer;
    }
    public long scanLong()throws IOException {
        long integer=0;
        int n=scan();
        while(isWhiteSpace(n))
        n=scan();
        long neg=1;
        if(n=='-')
        {
            neg=-1;
            n=scan();
        }
        while(!isWhiteSpace(n))
        {
            if(n>='0'&&n<='9')
            {
                integer*=10;
                integer+=n-'0';
                n=scan();
            }
            else throw new InputMismatchException();
        }
        return neg*integer;
    }
    public double scanDouble()throws IOException {
        double doub=0;
        int n=scan();
        while(isWhiteSpace(n))
        n=scan();
        int neg=1;
        if(n=='-') {
            neg=-1;
            n=scan();
        }
        while(!isWhiteSpace(n)&&n!='.') {
            if(n>='0'&&n<='9') {
                doub*=10;
                doub+=n-'0';
                n=scan();
            }
            else throw new InputMismatchException();
        }
        if(n=='.') {
            n=scan();
            double temp=1;
            while(!isWhiteSpace(n)) {
                if(n>='0'&&n<='9') {
                    temp/=10;
                    doub+=(n-'0')*temp;
                    n=scan();
                }
                else throw new InputMismatchException();
            }
        }
        return doub*neg;
    }
    public String scanString()throws IOException {
        StringBuilder sb=new StringBuilder();
        int n=scan();
        while(isWhiteSpace(n))
        n=scan();
        while(!isWhiteSpace(n)) {
            sb.append((char)n);
            n=scan();
        }
        return sb.toString();
    }
    private boolean isWhiteSpace(int n) {
        if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
        return true;
        return false;
    }
}
