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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.HashMap;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        List<List<Integer>> graph = new ArrayList<>();
        Map<Integer, Map<Integer, Integer>> colore = new HashMap<>();

        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            for (int i = 0; i < n; i++) {
                graph.add(new ArrayList<>());
            }
            List<Integer> order = new ArrayList<>();
            for (int i = 0; i < n - 1; i++) {
                int v, u;
                v = in.nextInt() - 1;
                u = in.nextInt() - 1;
                addEdge(v, u);
                addEdge(u, v);
                order.add(v);
                order.add(u);
            }
            int start = 0;
            for (int i = 0; i < n; i++) {
                if (graph.get(i).size() >= 3) {
                    int v = i;
                    for (int j = 0; j < graph.get(i).size(); j++) {
                        int u = graph.get(i).get(j);

                        if (!colore.containsKey(v))
                            colore.put(v, new HashMap<>());
                        colore.get(v).put(u, start);
                        if (!colore.containsKey(u))
                            colore.put(u, new HashMap<>());
                        colore.get(u).put(v, start);
                        start++;
                    }
                    break;
                }
            }

            for (int i = 0; i < order.size(); i += 2) {
                int v = order.get(i);
                int u = order.get(i + 1);
                if (colore.containsKey(v) && colore.get(v).containsKey(u)) {
                    out.println(colore.get(v).get(u));
                } else {
                    out.println(start);
                    start++;
                }
            }
        }

        private void addEdge(int v, int u) {
            graph.get(v).add(u);
        }

    }
}