Problem: You are given a tree with n nodes. You have to write non-negative integers on its edges so that the following condition would be satisfied:

For every two nodes i, j, look at the path between them and count the sum of numbers on the edges of this path. Write all obtained sums on the blackboard. Then every integer from 1 to ⌊ (2n^2)/(9) ⌋ has to be written on the blackboard at least once. 

It is guaranteed that such an arrangement exists.

Input

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of nodes.

Each of the next n-1 lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), meaning that there is an edge between nodes u and v. It is guaranteed that these edges form a tree.

Output

Output n-1 lines, each of form u v x (0 ≤ x ≤ 10^6), which will mean that you wrote number x on the edge between u, v. 

Set of edges (u, v) has to coincide with the set of edges of the input graph, but you can output edges in any order. You can also output ends of edges in an order different from the order in input.

Examples

Input


3
2 3
2 1


Output


3 2 1
1 2 2


Input


4
2 4
2 3
2 1


Output


4 2 1
3 2 2
1 2 3


Input


5
1 2
1 3
1 4
2 5


Output


2 1 1
5 2 1
3 1 3
4 1 6

Note

In the first example, distance between nodes 1 and 2 is equal to 2, between nodes 2 and 3 to 1, between 1 and 3 to 3.

In the third example, numbers from 1 to 9 (inclusive) will be written on the blackboard, while we need just from 1 to 5 to pass the test.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Codeforces1205D {

	//fuck why am i so bad at coding all graph problems i could have done this problem instead of B kappa
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int[][] edges = new int[n-1][2];
		for (int i = 0; i < n-1; i++) {
			st = new StringTokenizer(br.readLine());
			edges[i][0] = Integer.parseInt(st.nextToken())-1;
			edges[i][1] = Integer.parseInt(st.nextToken())-1;
		}
		int[][] adjacency = toadjacency(edges, n);
		
		//do the 1/3 2/3 split
		int[][] path = new int[n][2];
		int[] temp = BFSpath(adjacency, n, 0);
		for (int i = 0; i < n; i++) {
			path[i][0] = temp[i];
		}
		for (int i = 0; i < n; i++) {
			path[i][1] = i;
		}
		keysort(path, 0);
		
		//number of descendants including self
		int[] parent = BFSparentTree(adjacency, n, 0);
		int[] numdesc = new int[n];
		for (int i = n-1; i >= 0; i--) {
			numdesc[path[i][1]]++;
			if (i != 0) {
				numdesc[parent[path[i][1]]] += numdesc[path[i][1]];
			}
		}
		
		int index = -1;
		//find lowest index with numdesc at least n/3
		boolean bool = true;
		for (int i = n-1; (i >= 0) && (bool); i--) {
			if (3*numdesc[path[i][1]] >= n) {
				bool = false;
				index = path[i][1];
			}
		}
		int index2 = parent[index];
		
		//redo everything from index
		temp = BFSpath(adjacency, n, index);
		for (int i = 0; i < n; i++) {
			path[i][0] = temp[i];
		}
		for (int i = 0; i < n; i++) {
			path[i][1] = i;
		}
		keysort(path, 0);
		
		//number of descendants including self
		parent = BFSparentTree(adjacency, n, index);
		for (int i = 0; i < n; i++) {
			numdesc[i] = 0;
		}
		for (int i = n-1; i >= 0; i--) {
			numdesc[path[i][1]]++;
			if (i != 0) {
				numdesc[parent[path[i][1]]] += numdesc[path[i][1]];
			}
		}
		
		//ok now figure out which things are going into pile 1 vs pile 2
		boolean[] pile = new boolean[n];
		int size1 = 0;
		if (index != 0) {
			pile[index2] = true;
			size1 += numdesc[index2];
		}
		for (int i = 0; i < n; i++) {
			if ((parent[i] == index) && (i != index)) {
				if ((size1*3 < (n-3)) && !pile[i]) {
					pile[i] = true;
					size1 += numdesc[i];
				}
			}
		}
		
		for (int i = 1; i < n; i++) {
			if (pile[parent[path[i][1]]]) {
				pile[path[i][1]] = true;
			}
		}
		
		//System.out.println(index);
		//for (int i = 0; i < n; i++) {
		//	System.out.println(pile[i]);
		//}
		
		//ok once you have the 1/3 2/3 split just make one side like 1 through n/3 and the other side multiples of n/3 until 2n^2/9 and then the end yay!
		int[] q = new int[n];
		int ctr1 = 1;
		int ctr2 = 1;
		for (int i = 1; i < n; i++) {
			if (pile[path[i][1]]) {
				q[path[i][1]] = ctr1;
				ctr1++;
			}
			else {
				q[path[i][1]] = ctr2;
				ctr2++;
			}
		}
		
		for (int i = 0; i < n; i++) {
			if (i != index) {
				System.out.print((i+1) + " " + (parent[i]+1) + " ");
				if (pile[i]) {
					System.out.println(q[i] - q[parent[i]]);
				}
				else {
					System.out.println((q[i] - q[parent[i]]) * (size1+1));
				}
			}
		}
		

		pw.close();
	}
	
	public static void keysort(int[][] array, int index) {
    	int N = array.length;
    	if (N != 1) {
    		int[][] firstHalf = Arrays.copyOfRange(array, 0, N/2);
    		keysort(firstHalf, index);
        	int[][] secondHalf = Arrays.copyOfRange(array, N/2, N);
        	keysort(secondHalf, index);
        	int firstCounter = 0;
        	int secondCounter = 0;
        	for (int i = 0; i < N; i++) {
        		if (firstCounter == N/2) {
        			array[firstCounter+secondCounter] = secondHalf[secondCounter];
        			secondCounter++;
        		}
        		else if ((secondCounter == N-N/2) || firstHalf[firstCounter][index] <= secondHalf[secondCounter][index]) {
        			array[firstCounter+secondCounter] = firstHalf[firstCounter];
        			firstCounter++;
        		}
        		else {
        			array[firstCounter+secondCounter] = secondHalf[secondCounter];
        			secondCounter++;
        		}
        	}
    	}	
    }
	
	public static int[] BFSpath (int[][] adjacency, int v, int index) {
		boolean[] found = new boolean[v];
		found[index] = true;
		int[] path = new int[v];
		path[index] = 0;
		int[] indexList = new int[v];
		int start = 0;
		int end = 1;
		indexList[0] = index;
		while ((end < v) && (start < end)) {
			for (int i = 0; i < adjacency[indexList[start]].length; i++) {
				if (found[adjacency[indexList[start]][i]] == false) {
					found[adjacency[indexList[start]][i]] = true;
					indexList[end] = adjacency[indexList[start]][i];
					path[adjacency[indexList[start]][i]] = path[indexList[start]]+1;
					end++;
				}
			}
			start++;
		}
		return path;
	}
	
	//takes adjacency list and converts to list of pointers
	public static int[] BFSparentTree(int[][] adjacency, int v, int index) {
		boolean[] found = new boolean[v];
		found[index] = true;
		int[] indexList = new int[v];
		int[] parent = new int[v];
		int start = 0;
		int end = 1;
		indexList[0] = index;
		parent[index] = index;
		while ((end < v) && (start < end)) {
			for (int i = 0; i < adjacency[indexList[start]].length; i++) {
				if (found[adjacency[indexList[start]][i]] == false) {
					found[adjacency[indexList[start]][i]] = true;
					indexList[end] = adjacency[indexList[start]][i];
					parent[adjacency[indexList[start]][i]] = indexList[start];
					end++;
				}
			}
			start++;
		}
		return parent;
		
	}
	
	//converts list of edges to adjacency list
		public static int[][] toadjacency(int[][] list, int v) {
			int[] counter = new int[v];
			int n = list.length;
			for (int i = 0; i < n; i++) {
				counter[list[i][0]]++;
				counter[list[i][1]]++;
			}
			int[][] adjacency = new int[v][];
			for (int i = 0; i < v; i++) {
				adjacency[i] = new int[counter[i]];
			}
			int[] counter2 = new int[v];
			for (int i = 0; i < n; i++) {
				adjacency[list[i][0]][counter2[list[i][0]]] = list[i][1];
				counter2[list[i][0]]++;
				adjacency[list[i][1]][counter2[list[i][1]]] = list[i][0];
				counter2[list[i][1]]++;
			}
			
			return adjacency;
		}
	
}