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>
import java.io.*;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class DIV2C_Ehab_and_Path_etic_MEXs {

    private static final StreamTokenizer IN = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    private static final PrintWriter OUT = new PrintWriter(new OutputStreamWriter(System.out));

    private int n;
    private Map<Integer, List<Edge>> edges = new HashMap<>();
    private int[] ans;

    private class Edge {
        int index;
        int lable = -1;

        public Edge(int index) {
            this.index = index;
        }
    }

    private void input() {
        n = nextInt();
        ans = new int[n-1];
        Arrays.fill(ans, -1);

        for (int i = 0; i < n - 1; i++) {
            int u = nextInt();
            int v = nextInt();

            List<Edge> children = edges.getOrDefault(u, new ArrayList<>(8));
            children.add(new Edge(i));
            if (children.size() == 1) {
                edges.put(u, children);
            }

            children = edges.getOrDefault(v, new ArrayList<>(8));
            children.add(new Edge(i));
            if (children.size() == 1) {
                edges.put(v, children);
            }
        }
    }

    private void process() {
        AtomicInteger lable = new AtomicInteger(0);
        int root = -1;
        int maxChildren = Integer.MAX_VALUE;

        for (int i = 1; i < n; i++) {
            if (root == -1 || maxChildren < edges.get(i).size()) {
                root = i;
                maxChildren = edges.get(i).size();
            }
        }

        if (root != -1) {
            List<Edge> children = edges.get(root);
            for (int i = 0; i < children.size(); i++) {
                children.get(i).lable = i;
            }
        }

        edges.values().stream().flatMap(List::stream)
                .filter(e -> e.lable >= 0)
                .peek(e -> ans[e.index] = e.lable)
                .count();

        int mark = n - 2;

        for (int i = 0; i < n - 1; i++) {
            if (ans[i] == -1) {
                ans[i] = mark--;
            }
        }
    }

    private void output() {
        Arrays.stream(ans).forEach(System.out::println);
        OUT.flush();
    }

    private static int nextInt() {
        try {
            if (IN.nextToken() != StreamTokenizer.TT_EOF) {
                return (int) IN.nval;
            } else {
                throw new EOFException();
            }
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static String nextStr() {
        try {
            if (IN.nextToken() != StreamTokenizer.TT_EOF) {
                return IN.sval;
            } else {
                throw new EOFException();
            }
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public static void main(String[] args) throws IOException {
        DIV2C_Ehab_and_Path_etic_MEXs main = new DIV2C_Ehab_and_Path_etic_MEXs();
        main.input();
        main.process();
        main.output();
    }
}
