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.function.IntConsumer;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;

/**
 * Built using CHelper plug-in
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC(in, out);
        try {
            solver.solve();
        } catch (ExitException ignored) {
        }
        out.close();
    }

    static class TaskC {
        FastScanner sc;
        PrintWriter out;

        public TaskC(FastScanner sc, PrintWriter out) {
            this.sc = sc;
            this.out = out;
        }

        public void solve() {
            times(1, this::solve);
        }

        public void solve(int time) {
            int n = sc.nextInt();
            TaskC.Node[] nodes = new TaskC.Node[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new TaskC.Node();
            }
            TaskC.Edge[] edges = new TaskC.Edge[n - 1];

            for (int i = 1; i < n; i++) {
                TaskC.Node u = nodes[sc.nextInt() - 1];
                TaskC.Node v = nodes[sc.nextInt() - 1];
                TaskC.Edge edge = edges[i - 1] = new TaskC.Edge(u, v);

                u.edges.add(edge);
                v.edges.add(edge);
            }

            int value = 0;
            for (TaskC.Node node : nodes) {
                if (node.edges.size() > 2) {
                    for (TaskC.Edge edge : node.edges) {
                        edge.value = value++;
                    }
                    break;
                }
            }

            for (TaskC.Edge edge : edges) {
                if (edge.value == -1) edge.value = value++;
            }

            for (TaskC.Edge edge : edges) {
                writeln(edge.value);
            }
        }

        private void writeln(Object obj) {
            out.println(obj);
        }

        private void times(int n, IntConsumer consumer) {
            for (int i = 0; i < n; i++) {
                try {
                    consumer.accept(i);
                } catch (ExitException ignored) {
                }
            }
        }

        static class Node {
            List<TaskC.Edge> edges = new ArrayList<>();

        }

        static class Edge {
            TaskC.Node u;
            TaskC.Node v;
            int value;

            public Edge(TaskC.Node u, TaskC.Node v) {
                this.u = u;
                this.v = v;
                this.value = -1;
            }

        }

    }

    static class FastScanner {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public FastScanner(InputStream stream) {
            this.stream = stream;
        }

        int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) return -1;
            }
            return buf[curChar++];
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public String next() {
            int c = read();
            while (isSpaceChar(c)) c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

    }

    static class ExitException extends RuntimeException {
    }
}