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:
//package bfs;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
//public class FastReader {
 
//}

class FastReader
{
    BufferedReader br;
    StringTokenizer st;
 
    public FastReader()
    {
        br = new BufferedReader(new
                 InputStreamReader(System.in));
    }
 
    String next()
    {
        while (st == null || !st.hasMoreElements())
        {
            try
            {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException  e)
            {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
 
    int nextInt()
    {
        return Integer.parseInt(next());
    }
 
    long nextLong()
    {
        return Long.parseLong(next());
    }
 
    double nextDouble()
    {
        return Double.parseDouble(next());
    }
 
    String nextLine()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}

class Graph
{
    int n;
    List<List<Integer>> adjList;
    boolean visited[];
    int countNeighbours[],parent[];
    Graph(int nodes)
    {
        n=nodes;
        visited = new boolean[n];
        adjList = new ArrayList<>(n);
        countNeighbours = new int[n];
        parent = new int[n];
        Arrays.fill(parent,-1);
        for(int i=0;i<n;i++)
        {
            adjList.add(new ArrayList<>());
        }
    }
    void printList()
    {
        for(int i=0;i<n;i++)
        {
            System.out.print(i);
            List<Integer> list = adjList.get(i);
            for(int node:list)
            {
                
                System.out.print("->"+node);
            }
            System.out.println();
        }
    }
    int[] getNeighbours()
    {
        return countNeighbours;
    }
    void addEdge(int m,int n)
    {
        adjList.get(m).add(n);
        adjList.get(n).add(m);
        countNeighbours[m]++;
        countNeighbours[n]++;
    }
    int getRootNode()
    {
        int index=-1,max=0;
        for(int i=0;i<n;i++) 
        {
            if(countNeighbours[i]>max) {index=i;max=countNeighbours[i];}
        }
        return index;
    }
    void dfs(int start,boolean isLeafNode[])
    {
        visited[start]=true;
        //System.out.println(start+" ");
        List<Integer> adjNodes=adjList.get(start);
        boolean leafNode=true;
        for(int neighbour:adjNodes)
        {
            if(!visited[neighbour])
            {
                parent[neighbour]=start;
                leafNode=false;
                dfs(neighbour,isLeafNode);
            }
        }
        if(leafNode) isLeafNode[start]=true;
        else isLeafNode[start]=false;
        //return;
    }
}
class Pair{
    int x;
    int y;
    int wt;
    Pair(int i,int j){
        x=i;
        y=j;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Pair)) return false;
        Pair key = (Pair) o;
        return x == key.x && y == key.y;
    }
    @Override
    public int hashCode() {
        int result = x;
        result = 31*result + y;
        return result;
    }
}
public class Main
{
    public static void main(String args[])
    {
        FastReader sc = new FastReader();
        int n = sc.nextInt();
        Graph g = new Graph(n);
        HashMap<Pair,Integer> map = new HashMap<>();
        Pair p[] = new Pair[n-1];
        for(int i=0;i<n-1;i++)
        {
            int v1 = sc.nextInt()-1;int v2 = sc.nextInt()-1;g.addEdge(v1,v2);
            //map.put(new Pair(v1,v2),-1);
            p[i]=new Pair(v1,v2);
        }
        boolean leafNodes[] = new boolean[n];
        int root=g.getRootNode();
        g.dfs(root,leafNodes);
        //ArrayList<Integer> leaves = new ArrayList<>();
        HashSet<Integer> leaves = new HashSet<>();
        for(int i=0;i<n;i++) if(leafNodes[i]) {leaves.add(i);}
        int min=0;
        int curr=leaves.size();
        for(int i=0;i<n-1;i++)
        {
            if(leaves.contains(p[i].x)||leaves.contains(p[i].y)) {System.out.println(min);min++;}
            else {System.out.println(curr);curr++;}
        }
    }    
}