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.text.DecimalFormat;
import java.util.*;
import java.util.stream.IntStream;

public class Main {

    static {
        Locale.setDefault(Locale.ENGLISH);
    }

    private static DecimalFormat decimalFormat = new DecimalFormat("#0.00000000");

    private static class Reader implements Closeable {

        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public Reader() {
            reader = new BufferedReader(new InputStreamReader(System.in));
        }

        public Reader(String fileName) {
            try {
                reader = new BufferedReader(new FileReader(fileName));
            } catch (FileNotFoundException e) {
                throw new IllegalStateException("There is no file with given name");
            }
        }

        public String nextToken() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    String nextLine = reader.readLine();
                    if (nextLine == null) {
                        return null;
                    }
                    tokenizer = new StringTokenizer(nextLine);
                } catch (IOException e) {
                    throw new IllegalStateException("I/O Error");
                }
            }
            return tokenizer.nextToken();
        }

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

        public long nextLong() {
            return Long.parseLong(nextToken());
        }

        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }

        @Override
        public void close() throws IOException {
            reader.close();
        }
    }

    private static class Pair implements Comparable<Pair> {

        private int x;
        private int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        @Override
        public int compareTo(Pair o) {
            if (this.x != o.x) return Integer.compare(this.x, o.x);
            return Integer.compare(this.y, o.y);
        }
    }

    private <T> ArrayList<T> createArrayList(int n, T value) {
        ArrayList<T> result = new ArrayList<>();
        IntStream.range(0, n).forEach(i -> result.add(value));
        return result;
    }

    private static class Edge {

        private int v1, v2, n;

        public Edge(int v1, int v2, int n) {
            this.v1 = v1;
            this.v2 = v2;
            this.n = n;
        }

        public int getV1() {
            return v1;
        }

        public int getV2() {
            return v2;
        }

        public int getN() {
            return n;
        }

    }

    public static void main(String[] args) throws IOException {
        Reader reader = new Reader();
        //Reader reader = new Reader("input.txt");
        PrintWriter writer = new PrintWriter(System.out);
        new Main().solve(reader, writer);
        reader.close();
        writer.close();
    }

    private void solve(Reader reader, PrintWriter writer) {
        int n = reader.nextInt();
        ArrayList<Edge>[] edges = new ArrayList[100000];
        for (int i = 0; i < n; ++i) {
            edges[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; ++i) {
            int v1 = reader.nextInt() - 1;
            int v2 = reader.nextInt() - 1;
            edges[v1].add(new Edge(v1, v2, i));
            edges[v2].add(new Edge(v2, v1, i));
        }

        int[] result = new int[100000];
        Arrays.fill(result, -1);
        int counter = 0;
        for (int i = 0; i < n; ++i) {
            if (edges[i].size() == 1 && result[edges[i].get(0).n] == -1) {
                result[edges[i].get(0).n] = counter;
                counter++;
            }
        }
        for (int i = 0; i < n - 1; ++i) {
            if (result[i] == -1) {
                result[i] = counter;
                counter++;
            }
        }
        for (int i = 0; i < n - 1; ++i) {
            writer.println(result[i]);
        }
    }

}