A city consists of n junctions connected by n - 1 bidirectional roads so that any junction is reachable from any other junction by travelling the roads. Each road is colored by one of 26 colors, represented by lowercase English letters between 'a' and 'z'.
For each pair of junctions u and v there is only one simple path connecting them. Let us define the signature of this path as the string of letters that is obtained by writing down the letters corresponding to edges in the 
path in this order. Note that the signature of the path from v to u is the same as reversed signature of the path from u to v.
Given 
signatures of all different paths between junctions, reconstruct the road structure of the city.
The first line of the input contains one integer n (2 ≤ n ≤ 100) — number of junctions in the city. Next 
lines contain signatures of paths. i-th of those lines contain two space-separated integers ui, vi (1 ≤ ui, vi ≤ n) and a string of lowercase Latin letters — the signature of the path from ui to vi.
You may assume that exactly one of two paths (ui, vi) and (vi, ui) is represented in the input data. It is guaranteed that there is at least one possible solution for the given data.
Print n - 1 line. On j-th of those lines print aj bj cj, where aj, bj are the numbers of junctions connected by the road j, and cj is a letter that describes the color of the road. Roads can be listed in any order, as well as endpoints of any particular road.
3
1 2 a
1 3 b
2 3 ab
1 2 a
1 3 b
2
2 1 a
2 1 a
