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 Ehab_1325C {
    public static void main(String[] args) throws Exception{
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }
 
    static class TaskA {
        int n;
	List<List<Integer>> adj;
	int[][] valMap;
	
        public void fill(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
	    valMap = new int[n][3];
	    adj = new ArrayList<List<Integer>>();
	    for (int i = 0; i <= n; i++) {
		adj.add(new ArrayList<Integer>());
	    }

	    for (int i = 0; i < n-1; i++) {
		int u = in.nextInt();
		int v = in.nextInt();
		adj.get(u).add(v);
		adj.get(v).add(u);

		valMap[i][0] = u;
		valMap[i][1] = v;		
	    }
        }

	public void display(PrintWriter out) {
	    for (int i = 0; i < n; i++) {
		out.print(i + " ");
		for (Integer v : adj.get(i)) {
		    out.print(v + " ");
		}

		out.println();
	    }
	}

	public boolean isSame(int i, int x, int u, int v) {
	    if ((i == u && x == v) || (i == v && x== u)) {
		return true;
	    }
	    return false;
	}

        public void solve(int testNumber, InputReader in, PrintWriter out) throws Exception{
            fill(testNumber, in, out);
	    int i;
	    List<Integer> adju, adjSelected = null;
	    for (i = 1; i <= n; i++) {
		adju = adj.get(i);
		if (adju.size() >= 3) {
		    adjSelected = adju;
		    break;
		}
	    }

	    int x=0, y=0, z=0, startAt = 0;
	    if (adjSelected != null) {
		x = adjSelected.get(0);
		y = adjSelected.get(1);
		z = adjSelected.get(2);
		startAt = 3;

	    }

	    for (int j = 0; j < n-1; j++) {
		int u = valMap[j][0];
		int v = valMap[j][1];

		if (adjSelected != null) {
		    if (isSame(i, x, u, v)) {
			valMap[j][2] = 0;
		    } else if (isSame(i, y, u, v)) {
			valMap[j][2] = 1;
		    } else if (isSame(i, z, u, v)) {
			valMap[j][2] = 2;
		    } else {
			valMap[j][2] = startAt++;
		    }
		} else {
		    valMap[j][2] = startAt++;
		}
	    }
	    for (int j = 0; j < n-1; j++) {
		int u = valMap[j][0];
		int v = valMap[j][1];

		out.println(valMap[j][2]);
	    }

        }
    }
 
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
    }
 
 
}