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 mex {
    public static void main(String[] args) throws Exception {
        R in = new R();
        int n=in.nextInt();
        int[][] uv = in.next2Dint(n-1);
        if (n<=3) {
            for (int i = 0; i < n - 1; i++) {
                System.out.println(i);
            }
            return;
        }

        ArrayList<ArrayList<Integer>> conni = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            conni.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            conni.get(uv[i][0]-1).add(i);
            conni.get(uv[i][1]-1).add(i);
        }
        int[] values = new int[n];
        ArrayList<Integer> vals = new ArrayList<>();
        for (ArrayList<Integer> integers : conni) {
            if (integers.size() >= 3) {
                for (int i = 0; i < 3; i++) {
                    values[integers.get(i)]=i;
                    vals.add(integers.get(i));
                }
                break;
            }
        }
        int ct = vals.size();
        StringBuilder b = new StringBuilder();
        for (int i = 0; i < n-1; i++) {
            if (!vals.contains(i)) {
                b.append(ct);
                ct++;
            } else {
                b.append(values[i]);
            }
            b.append('\n');
        }

        System.out.print(b.toString());
        System.out.flush();
    }
    //<editor-fold desc="R">

    /**
     * This class is for fast input. Please ignore.
     */
    public static class R {
        private BufferedReader br;
        /**
         * Should be set to null at end of line
         */
        private StringTokenizer st;

        public R() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public R(String filename) throws IOException {
            br = new BufferedReader(new FileReader(filename + ".in"));
        }

        public R(BufferedReader reader) {
            br = reader;
        }

        public BufferedReader getReader() {
            return br;
        }

        public StringTokenizer getStringTokenizer() {
            return st;
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                String s = br.readLine();
                if (s == null) return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

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

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        /**
         * Note:
         * CAN MODIFY the BufferedReader's location and the string tokenizer!!!
         * Recommended to only use with next().
         */
        public boolean lineHasNext() throws IOException {
            if (st == null) {
                String s = br.readLine();
                if (s == null) return false;
                st = new StringTokenizer(s);
            }
            return st.hasMoreTokens();
        }

        /**
         * Note:
         * CAN MODIFY the BufferedReader's location and the string tokenizer!!!
         * Recommended to only use with next().
         */
        public boolean hasNext() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                String s = br.readLine();
                if (s == null) return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        /**
         * Skips a line. Sets st to null if has tokens left, and otherwise
         * reads a line.
         */
        public void skipLine() throws IOException {
            if (st == null || !st.hasMoreTokens()) {
                br.readLine(); // Otherwise, would do nothing.
            }
            st = null;
        }

        /**
         * This will set st to null, and this ignores current line
         */
        public String[] nextLine() throws IOException {
            String s = br.readLine();
            if (s == null) return null;
            st = new StringTokenizer(s);
            ArrayList<String> result = new ArrayList<>();
            while (st.hasMoreTokens()) {
                result.add(st.nextToken());
            }
            st = null;
            return result.toArray(new String[0]);
        }

        /**
         * sets st to null!
         */
        public String[] nextTower(int lines) throws IOException {
            String[] tower = new String[lines];
            st = null;
            for (int i = 0; i < lines; i++) {
                tower[i] = br.readLine();
            }
            return tower;
        }

        public int[] nextIntLine() throws IOException {
            return intArr(nextLine());
        }

        public long[] nextLongLine() throws IOException {
            return longArr(nextLine());
        }

        public int[] nextIntTower(int lines) throws IOException {
            return intArr(nextTower(lines));
        }

        public long[] nextLongTower(int lines) throws IOException {
            return longArr(nextTower(lines));
        }

        public int[] intArr(String[] strings) throws IOException {
            int[] ints = new int[strings.length];
            int i = 0;
            for (String s : strings) {
                ints[i] = Integer.parseInt(s);
                i++;
            }
            return ints;
        }

        public long[] longArr(String[] strings) throws IOException {
            long[] longs = new long[strings.length];
            int i = 0;
            for (String s : strings) {
                longs[i] = Long.parseLong(s);
                i++;
            }
            return longs;
        }

        public double[] doubleArr(String[] strings) {
            double[] doubles = new double[strings.length];
            int i = 0;
            for (String s : strings) {
                doubles[i] = Double.parseDouble(s);
                i++;
            }
            return doubles;
        }

        /**
         * This will set st to null
         */
        public char[] nextCharArray() throws IOException {
            st = null;
            String s = br.readLine();
            return s == null ? null : s.toCharArray();
        }

        /**
         * This will set st to null
         * Boolean at pos i true if char at pos i == c
         */
        public boolean[] nextBoolArray(char c) throws IOException {
            char[] chars = nextCharArray();
            if (chars == null) return null;
            boolean[] booleans = new boolean[chars.length];
            for (int i = 0; i < chars.length; i++) {
                booleans[i] = chars[i] == c;
            }
            return booleans;
        }

        public int[][] next2Dint(int lines) throws IOException {
            int[][] result = new int[lines][];
            for (int i = 0; i < lines; i++) {
                result[i] = nextIntLine();
            }
            return result;
        }

        public long[][] next2Dlong(int lines) throws IOException {
            long[][] result = new long[lines][];
            for (int i = 0; i < lines; i++) {
                result[i] = nextLongLine();
            }
            return result;
        }

        public char[][] next2Dchar(int lines) throws IOException {
            char[][] result = new char[lines][];
            for (int i = 0; i < lines; i++) {
                result[i] = nextCharArray();
            }
            return result;
        }

        public boolean[][] next2Dbool(int lines, char c) throws IOException {
            boolean[][] result = new boolean[lines][];
            for (int i = 0; i < lines; i++) {
                result[i] = nextBoolArray(c);
            }
            return result;
        }
    }
    //</editor-fold>
}