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.*;
public class d {
    public static void main(String[] args) throws IOException {
        //Scanner s = new Scanner(System.in);
                BufferedReader s=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        StringBuilder sb1=new StringBuilder();
       int n=Integer.parseInt(s.readLine().trim().split("\\s+")[0]);
     ArrayList<Integer> [] adj=new ArrayList[n+1];

        val=new HashMap[n+1];int[]    vis1=new int[n+1];vis=new int[n+1];
        int[] U=new int[n-1];int [] V=new int[n-1];
        for(int i = 0; i<n-1; i++){
            String[] st=s.readLine().trim().split("\\s+");
            int u=Integer.parseInt(st[0]);int v=Integer.parseInt(st[1]);
            if(adj[u]==null) adj[u]=new ArrayList<>();
            if(adj[v]==null) adj[v]=new ArrayList<>();
            U[i]=u;V[i]=v;
            adj[u].add(v);adj[v].add(u);
            vis1[u]++;vis1[v]++;
        }
        ArrayList<Integer> ad=new ArrayList<>();int x=0;int ele=0;
        for(int i=1;i<=n;i++){
            if(vis1[i]==1){
             if(ad.size()==0) ele=i;
             ad.add(i);vis[i]=1;
         }
        }
        for(int j:ad){
            if(x==n-1){

            }else{
                if(val[j]==null) val[j]=new HashMap<>();
                if(val[adj[j].get(0)]==null) val[adj[j].get(0)]=new HashMap<>();

                val[j].put(adj[j].get(0),x);
         val[adj[j].get(0)].put(j,x++);}
        }y=n-2;
        dfs(x,adj[ele].get(0),adj);
          for(int i=0;i<n-1;i++){
              sb.append(val[U[i]].get(V[i])+"\n");
          }
        System.out.println(sb.toString());
    }static HashMap<Integer,Integer>[] val;static int[] vis;static int y;
    static void dfs(int x ,int i,ArrayList<Integer>[] adj){
      vis[i]=1;
        if(y>=x) {
        //    System.out.println("HI");
            Queue<Integer> q=new LinkedList<>();
             for(int j:adj[i]){
         //        System.out.println(i+" "+j+" "+y);
                 if(val[i]==null) val[i]=new HashMap<>();    if(val[j]==null) val[j]=new HashMap<>();
                 if(vis[j]==0&&!val[i].containsKey(j)){
                     val[i].put(j,y);
                     val[j].put(i,y--);
                     //      System.out.println("HI");
                     q.add(j);

                 }if(vis[j]==0) {
                 }
             }
       while (!q.isEmpty()){int j=q.poll();
                 if(vis[j]==0) dfs(x,j,adj);
        }
        }else{
            for(int j:adj[i]){
                if(val[i]==null) val[i]=new HashMap<>();    if(val[j]==null) val[j]=new HashMap<>();
                if(!val[i].containsKey(j)&&vis[j]==0){

                    val[i].put(j,0);
                    val[j].put(i,0);
            return;
                }

                return;
            }
        }}

    static  void computeLPSArray(String pat, int M, int lps[]) {
        int len = 0;
        int i = 1;
        lps[0] = 0;
        while (i < M) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            }
            else
            {
                if (len != 0) {
                    len = lps[len - 1];
                }
                else
                {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }
    static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;

        if (n % 2 == 0 || n % 3 == 0) return false;

        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;

        return true;
    }
    static long powerwithmod(long  x, long y, int p) {
        long  res = 1;
        x = x % p;
        while (y > 0) {
            if ((y & 1) == 1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }
    static long  powerwithoutmod(long x, int y) {
        long  temp;
        if( y == 0)
            return 1;
        temp = powerwithoutmod(x, y/2);
        if (y%2 == 0)
            return temp*temp;
        else
        {
            if(y > 0)
                return x * temp * temp;
            else
                return (temp * temp) / x;
        }
    }
    static void fracion(double x) {
        String a = "" + x;
        String spilts[] = a.split("\\."); // split using decimal
        int b = spilts[1].length(); // find the decimal length
        int denominator = (int) Math.pow(10, b); // calculate the denominator
        int numerator = (int) (x * denominator); // calculate the nerumrator Ex
        // 1.2*10 = 12
        int gcd = (int) gcd((long) numerator, denominator); // Find the greatest common
        // divisor bw them
        String fraction = "" + numerator / gcd + "/" + denominator / gcd;
        // System.out.println((denominator/gcd));
        long x1 = modInverse(denominator / gcd, 998244353);
        //  System.out.println(x1);
        System.out.println((((numerator / gcd) % 998244353 * (x1 % 998244353)) % 998244353));
    }
    static int bfs(int i1, ArrayList<Integer>[] h, int[] vis, int n,int val1) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(i1);Queue<Integer> aq=new LinkedList<Integer>();
        aq.add(0);
        while(!q.isEmpty()){
            int i=q.poll();
            int val=aq.poll();
            if(i==n){
                return val;
            }
            if(h[i]!=null){
                for(Integer j:h[i]){
                    if(vis[j]==0){
                        q.add(j);vis[j]=1;
                        aq.add(val+1);}
                }
            }
        }return -1;
    }
    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    static long modInverse(long a, int m)
    {
        return (powerwithmod(a, m - 2, m));
    }
    static int MAXN=100001;
    static int[] spf=new int[MAXN];
    static void sieve() {
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)
            spf[i] = i;
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;
        for (int i=3; i*i<MAXN; i++)
        {
            if (spf[i] == i)
            {
                for (int j=i*i; j<MAXN; j+=i)

                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }
    static Vector<Integer> getFactorizationUsingSeive(int x) {
        Vector<Integer> ret = new Vector<Integer>();
        while (x != 1)
        {
            ret.add(spf[x]);
            x = x / spf[x];
        }
        return ret;
    }
   /* static long[] fac = new long[MAXN+1];
     static void calculatefac(int mod){
        for (int i = 1 ;i <= MAXN; i++)
            fac[i] = fac[i-1] * i % mod;
     }
      static long nCrModPFermat(int n, int r, int mod) {
         if (r == 0)
            return 1;
        fac[0] = 1;
        return (fac[n]* modInverse(fac[r], mod)
                % mod * modInverse(fac[n-r], mod)
                                    % mod) % mod;
    } */}
class Student {
    int l;int r;
    public Student(int l, int r) {
        this.l = l;
        this.r = r;
    }

    public String toString()
    {
        return this.l+" ";
    }
}
class Sortbyroll implements Comparator<Student> {

    public int compare(Student a, Student b){
        if(a.l==b.l) return a.r-b.r;
        return b.l-a.l;  }
}
class Sortbyroll1 implements Comparator<Student> {
    public int compare(Student a, Student b){
        if(a.r==b.r) return a.l-b.l;
        return b.l-a.l;
    }
}