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.*;
// tau is superior

public class C
{
    class Edge
    {
        int v, id;
        Edge(int vv, int ii)
        {
            v = vv;
            id = ii;
        }
    }

    int dfs(int u, int p)
    {
        int num = 1;
        for (Edge e : adj[u])
        {
            if (e.v == p)
                continue;

            int val = dfs(e.v, u);
            num += val;

            long here = val;
            here *= (n - val);
            here /= 2;
            block[e.id] = here;
        }

        return num;
    }

    ArrayList<Edge>[] adj;
    long[] block;
    int n;

    void solve(FastIO io)
    {
        n = io.nextInt();
      
        adj = new ArrayList[n];

        for (int i = 0; i < n; i++)
            adj[i] = new ArrayList<>();

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

            adj[u].add(new Edge(v, i));
            adj[v].add(new Edge(u, i));
        }

        block = new long[n - 1];

        dfs(0, -1);

        Integer[] sort = new Integer[n - 1];
        for (int i = 0; i < n - 1; i++)
            sort[i] = i;

        Arrays.sort(sort, (a, b) -> Long.compare(block[a], block[b]));
        int[] out = new int[n-1];
        for (int i = 0; i < n-1; i++)
            out[sort[i]] = i;

        for (int i = 0; i < n-1; i++)
            io.println(out[i]);
        
    }

    public static void main(String[] args) {
        FastIO io = new FastIO();

        new C().solve(io);

        io.close();
    }

    static class FastIO extends PrintWriter
    {
        StringTokenizer st = new StringTokenizer("");
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

        FastIO()
        {
            super(System.out);
        }

        String next()
        {
            while (!st.hasMoreTokens())
            {
                try {
                    st = new StringTokenizer(r.readLine());
                } catch (Exception e) { }
            }
            return st.nextToken();
        }

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

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

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