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 Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int INF = (int) (1e9 + 10);
    static final int MOD = (int) (1e9 + 7);
    static final int N = (int) (1e3);
    static final int LOGN = 20;
    static Edge[] edges;
    static ArrayList<Integer>[] g;

    static class Edge {
        int v, u;

        Edge(int v, int u) {
            this.v = Math.min(v, u);
            this.u = Math.max(v, u);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge edge = (Edge) o;
            return v == edge.v &&
                    u == edge.u;
        }

        @Override
        public int hashCode() {
            return Objects.hash(v, u);
        }
    }

    static void solve() {
        int n = in.nextInt();

        edges = new Edge[n - 1];
        g = new ArrayList[n];
        Arrays.setAll(g, gg -> new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {
            int v = in.nextInt() - 1;
            int u = in.nextInt() - 1;
            edges[i] = new Edge(v, u);
            g[v].add(u);
            g[u].add(v);
        }

        if (n == 2) {
            out.println(0);
            return;
        } else if (n == 3) {
            out.println(0);
            out.println(1);
            return;
        }

        ArrayList<Integer> leafs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (g[i].size() == 1) {
                leafs.add(i);
            }
        }


        if (leafs.size() > 2) {
            boolean[] are = new boolean[n];
            for (int i = 0; i < 3; i++) {
                are[leafs.get(i)] = true;
            }
            int cnt1 = 0, cnt2 = 3;
            for (int i = 0; i < n - 1; i++) {
                Edge e = edges[i];
                if (are[e.v] || are[e.u]) {
                    out.println(cnt1++);
                } else {
                    out.println(cnt2++);
                }
            }

        } else {
            for (int i = 0; i < n - 1; i++) {
                out.println(i);
            }
        }

    }

    public static void main(String[] args) throws FileNotFoundException {
        in = new FastReader(System.in);
//        in = new FastReader(new FileInputStream("connect.in"));
        out = new PrintWriter(System.out);
//        out = new PrintWriter(new FileOutputStream("connect.out"));


        int q = 1;
//        q = in.nextInt();

        while (q-- > 0) {
            solve();
        }

        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        Integer nextInt() {
            return Integer.parseInt(next());
        }

        Long nextLong() {
            return Long.parseLong(next());
        }

        Double nextDouble() {
            return Double.parseDouble(next());
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }
}