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.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    static class Pair {
        int v;
        int pos;

        public Pair(int v, int pos) {
            this.v = v;
            this.pos = pos;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        if (n == 2) {
            System.out.println("0");
            return;
        }

        List<List<Pair>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            tree.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            String[] line = bf.readLine().split("\\s");
            int u = Integer.parseInt(line[0])-1;
            int v = Integer.parseInt(line[1])-1;
            tree.get(u).add(new Pair(v,i));
            tree.get(v).add(new Pair(u,i));
        }
        List<Integer> leafs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (tree.get(i).size() == 1){
                leafs.add(i);
            }
        }
        int[] ans = new int[n-1];
        Arrays.fill(ans,-1);
        for (int i = 0; i < leafs.size(); i++) {
            ans[tree.get(leafs.get(i)).get(0).pos] = i;
        }
        int c = leafs.size();
        for (int i = 0; i < ans.length; i++) {
            if (ans[i] == -1){
                ans[i] = c++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int an : ans) {
            sb.append(an).append('\n');
        }
        System.out.println(sb);
    }
}