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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
import java.util.function.*;
import java.util.stream.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;


public class C {

    private static final FastReader in = new FastReader();
    private static final FastWriter out = new FastWriter();

    public static void main(String[] args) {
        new C().run();
    }

    private void run() {
        var t = 1;
        while (t-- > 0) {
            solve();
        }

        out.flush();
    }

    private void solve() {
        var n = in.nextInt();

        var tree = Graph.ofInt(n);
        for (var i = 0; i < n - 1; i++) {
            var u = in.nextInt() - 1;
            var v = in.nextInt() - 1;
            tree.addBidirectedEdges(u, v, i);
        }

        var ans = new int[n - 1];
        Arrays.fill(ans, -1);

        var degree = new int[n];
        var q = new LinkedList<Integer>();
        for (var i = 0; i < n; i++) {
            degree[i] = tree.degree(i);
            if (degree[i] == 1) {
                q.offer(i);
            }
        }

        var label = 0;
        while (!q.isEmpty()) {
            var u = q.poll();
            for (var e : tree.neighbors(u)) {
                if (ans[e.weight] == -1) {
                    ans[e.weight] = label++;
                    degree[e.neighbor]--;
                    if (degree[e.neighbor] == 1) {
                        q.offer(e.neighbor);
                    }
                }
            }
        }

        for (var l : ans) {
            out.println(l);
        }
    }

}


class FastReader {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer in;

    public String next() {
        while (in == null || !in.hasMoreTokens()) {
            try {
                in = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                return null;
            }
        }
        return in.nextToken();
    }

    public BigDecimal nextBigDecimal() {
        return new BigDecimal(next());
    }

    public BigInteger nextBigInteger() {
        return new BigInteger(next());
    }

    public boolean nextBoolean() {
        return Boolean.valueOf(next());
    }

    public byte nextByte() {
        return Byte.valueOf(next());
    }

    public double nextDouble() {
        return Double.valueOf(next());
    }

    public double[] nextDoubleArray(int length) {
        var a = new double[length];
        for (var i = 0; i < length; i++) {
            a[i] = nextDouble();
        }
        return a;
    }

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

    public int[] nextIntArray(int length) {
        var a = new int[length];
        for (var i = 0; i < length; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    public long nextLong() {
        return Long.valueOf(next());
    }

    public long[] nextLongArray(int length) {
        var a = new long[length];
        for (var i = 0; i < length; i++) {
            a[i] = nextLong();
        }
        return a;
    }

}


class FastWriter extends PrintWriter {

    public FastWriter() {
        super(System.out);
    }

    public void println(double[] a) {
        for (var i = 0; i < a.length; i++) {
            print(a[i]);
            print(i + 1 < a.length ? ' ' : '\n');
        }
    }

    public void println(int[] a) {
        for (var i = 0; i < a.length; i++) {
            print(a[i]);
            print(i + 1 < a.length ? ' ' : '\n');
        }
    }

    public void println(long[] a) {
        for (var i = 0; i < a.length; i++) {
            print(a[i]);
            print(i + 1 < a.length ? ' ' : '\n');
        }
    }

    public <T> void println(T[] a) {
        for (var i = 0; i < a.length; i++) {
            print(a[i]);
            print(i + 1 < a.length ? ' ' : '\n');
        }
    }

    public <T> void println(List<T> l) {
        println(l.toArray());
    }

    public void debug(String name, Object o) {
        String value = Arrays.deepToString(new Object[] { o });
        value = value.substring(1, value.length() - 1);
        System.err.println(name + " => " + value);
    }

}


class Graph<T> {

    public final int nodes;
    private final List<List<Edge<T>>> adjacencyList;
    private final T defaultWeight;

    Graph(int nodes, T defaultWeight) {
        this.nodes = nodes;
        this.adjacencyList = new ArrayList<>(nodes);
        this.defaultWeight = defaultWeight;

        for (var i = 0; i < nodes; i++) {
            this.adjacencyList.add(new ArrayList<>());
        }
    }

    public static Graph<Integer> ofInt(int nodes) {
        return new Graph<Integer>(nodes, 1);
    }

    public static Graph<Double> ofDouble(int nodes) {
        return new Graph<Double>(nodes, 1.0);
    }

    public void addEdge(int u, int v) {
        addEdge(u, v, defaultWeight);
    }

    public void addEdge(int u, int v, T weight) {
        adjacencyList.get(u).add(Edge.of(v, weight));
    }

    public void addBidirectedEdges(int u, int v) {
        addBidirectedEdges(u, v, defaultWeight);
    }

    public void addBidirectedEdges(int u, int v, T weight) {
        addEdge(u, v, weight);
        addEdge(v, u, weight);
    }

    public List<Edge<T>> neighbors(int u) {
        return adjacencyList.get(u);
    }

    public int degree(int u) {
        return neighbors(u).size();
    }

    @Override
    public String toString() {
        String adj = IntStream.range(0, nodes)
                .mapToObj(i -> "    " + i + ": " + adjacencyList.get(i))
                .collect(Collectors.joining(",\n"));
        return "Graph {\n"
                + "  nodes: " + nodes + ",\n"
                + "  adjacencyList: {\n"
                + adj + "\n"
                + "  }\n"
                + "}";
    }

    public static class Edge<T> {

        public final int neighbor;
        public final T weight;

        Edge(int neighbor, T weight) {
            this.neighbor = neighbor;
            this.weight = weight;
        }

        public static <T> Edge<T> of(int neighbor, T weight) {
            return new Edge<>(neighbor, weight);
        }

        public int getNeighbor() {
            return neighbor;
        }

        public T getWeight() {
            return weight;
        }

        @Override
        public String toString() {
            return String.format("(%s, %s)", neighbor, weight);
        }

    }

}


class IntPair extends Pair<Integer, Integer> {

    IntPair(Integer a, Integer b) {
        super(a, b);
    }

    public static IntPair of(int a, int b) {
        return new IntPair(a, b);
    }

}

class Pair<T, U> {

    public T a;
    public U b;

    Pair(T a, U b) {
        this.a = a;
        this.b = b;
    }

    public static <T, U> Pair<T, U> of(T a, U b) {
        return new Pair<>(a, b);
    }

    public T getA() {
        return a;
    }

    public U getB() {
        return b;
    }

    @Override
    public String toString() {
        return String.format("(%s, %s)", a, b);
    }

}