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.IOException;
import java.io.InputStream;
import java.util.*;
public class Solution {
    /*static ArrayList<Integer> ar[];
    static boolean vis[];
    static void dfs(int s) {
        vis[s]=true;
        c++;
        for(int j=0;j<ar[s].size();j++) {
            if(vis[ar[s].get(j)]==false)
                dfs(ar[s].get(j));
        }
    }*/
    /*static void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1; 
        int n2 = r - m; 
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 
        for (int i=0; i<n1; ++i) 
            L[i] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 
        int i = 0, j = 0, k=1;  
        while (i < n1 && j < n2) { 
            if (L[i] <= R[j]) { 
                arr[k] = L[i]; 
                i++; 
            } 
            else { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
        while (i < n1) { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
        while (j < n2) { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
    static void sort(int arr[], int l, int r) { 
        if (l < r) {  
            int m = (l+r)/2;  
            sort(arr, l, m); 
            sort(arr , m+1, r); 
            merge(arr, l, m, r); 
        } 
    }*/
    public static void main(String args[])throws Exception {
        FastReader in = new FastReader(System.in);    
        int q = 1,i,j;
        StringBuilder sb = new StringBuilder();
            int n=in.nextInt(),res=0;
            ArrayList<Integer> tree[]=new ArrayList[n+1];
            for(i=0;i<=n;i++)
                tree[i]=new ArrayList<Integer>();
            ArrayList<Integer> ar[]=new ArrayList[n+1];
            for(i=0;i<=n;i++)
                ar[i]=new ArrayList<Integer>(); 
            int ans[]=new int[n];
            for(i=1;i<n;i++) {
                int x=in.nextInt();
                int y=in.nextInt();
                tree[x].add(y);
                tree[y].add(x);
                ar[x].add(i);
                ar[y].add(i);
            }
            HashSet<Integer> s=new HashSet<>();
            for(i=1;i<=n;i++) {
                if(tree[i].size()>2) {
                    res=1;
                    s.add(ar[i].get(0));
                    s.add(ar[i].get(1));
                    s.add(ar[i].get(2));
                    ans[ar[i].get(0)]=0;
                    ans[ar[i].get(1)]=1;
                    ans[ar[i].get(2)]=2;
                    break;
                }
            }
            if(res==0) {
                for(i=0;i<n-1;i++)
                    sb.append(i+"\n");
            }
            else {
                int k=3;
                for(i=1;i<n;i++) {
                    if(!s.contains(i))
                        ans[i]=k++;
                    sb.append(ans[i]+"\n");
                }
            }
            //sb.append(res+"\n");
            //System.out.println(res);
        
        System.out.println(sb);
    }
}
class FastReader {
    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;
    FastReader(InputStream is) {
        in = is;
    }
    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }
    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }
    String nextLine() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c != 10 && c != 13; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }
    char nextChar() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        return (char) c;
    }
    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}