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

/**
 * 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;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CEhabAndPathEticMEXs solver = new CEhabAndPathEticMEXs();
        solver.solve(1, in, out);
        out.close();
    }

    static class CEhabAndPathEticMEXs {
        int MAXN = 200005;
        PrintWriter out;
        InputReader in;
        ArrayList<Edge>[] tree = new ArrayList[MAXN];
        int[] sz = new int[MAXN];
        long[] ans = new long[MAXN];
        int n;
        final Comparator<Tuple> com = new Comparator<Tuple>() {
            public int compare(Tuple t1, Tuple t2) {
                if (t1.x != t2.x)
                    return Long.compare(t1.x, t2.x);
                else
                    return Integer.compare(t1.y, t2.y);
            }
        };

        void dfs(int v, int p) {
            sz[v] = 1;
            for (Edge e : tree[v]) {
                int u = e.other(v);
                if (u != p) {
                    dfs(u, v);
                    sz[v] += sz[u];
                }
            }
        }

        void dfs1(int v, int p) {
            for (Edge e : tree[v]) {
                int u = e.other(v);
                if (u != p) {
                    ans[e.wt] = (long) sz[u] * (long) (n - sz[u]);
                    dfs1(u, v);
                }
            }
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.out = out;
            this.in = in;
            n = ni();
            int i = 0;
            for (i = 0; i < n; i++)
                tree[i] = new ArrayList<>();
            for (i = 0; i < n - 1; i++) {
                int u = ni() - 1;
                int v = ni() - 1;
                Edge e = new Edge(u, v, i);
                tree[u].add(e);
                tree[v].add(e);
            }
            dfs(0, -1);
            dfs1(0, -1);
            Tuple[] hola = new Tuple[n - 1];
            for (i = 0; i < n - 1; i++)
                hola[i] = new Tuple(ans[i], i);
            Arrays.sort(hola, com);
            int[] lol = new int[n - 1];
            int p = n - 2;
            for (i = 0; i < n - 1; i++, p--)
                lol[hola[i].y] = i;
            for (i = 0; i < n - 1; i++)
                pn(lol[i]);
        }

        int ni() {
            return in.nextInt();
        }

        void pn(long zx) {
            out.println(zx);
        }

        class Tuple {
            long x;
            int y;

            Tuple(long a, int b) {
                x = a;
                y = b;
            }

        }

        class Edge {
            int u;
            int v;
            int wt;

            Edge(int a, int b, int w) {
                u = a;
                v = b;
                wt = w;
            }

            int other(int a) {
                return u ^ v ^ a;
            }

        }

    }

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

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

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

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

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

            return res.toString();
        }

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

    }
}