Робот потерялся в большом городе. Город представляет собой совокупность n перекрёстков и двусторонних дорог, соединяющих некоторые из пары них. Всего в городе n - 1 дорога, гарантируется, что от любого перекрёстка можно добраться до любого другого, передвигаясь только по дорогам. Каждая дорога окрашена в один из 26-ти цветов, обозначаемых маленькими латинскими буквами (от 'a' до 'z').
Робот бродит по городу уже довольно давно и успел собрать некоторую статистику. А именно, пусть u, v – два различных перекрёстка в городе. Робот знает, что в данных ограничениях между этими двумя перекрёстками существует ровно один простой путь (то есть не проходящий ни по каким вершинам более чем единожды) по дорогам. Назовём меткой этого пути последовательность цветов дорог в порядке следования от u до v, записанную без каких-либо разделителей как строка латинских букв. Робот перебрал все пары различных перекрёстков и выписал для каждой из них метку соответствующего пути.
Заметим, что если известна метка s пути от u до v, то метка обратного пути есть просто развёрнутая строка s. Поэтому из всех n(n - 1) упорядоченных пар робот сообщает Вам только 
, исключая обратные пути.
Вам нужно помочь роботу и составить подробный план города, описав все имеющиеся в городе дороги.
В первой строке задано число n (2 ≤ n ≤ 100) – количество перекрёстков в городе. В следующих строках содержится информация о метках некоторых путей. В i-ой из этих строк содержатся через пробел два числа ui, vi (1 ≤ ui, vi ≤ n) и строка si, состоящая только из маленьких латинских букв, задающая метку ориентированного пути от ui до vi.
Гарантируется, что не существует i и j таких, что ui = vj и vi = uj, то есть каждая пара задана ровно единожды. Также гарантируется, что робот Вас нигде не обманул, и требуемый план города существует.
Выведите n - 1 строку, в j-ой из которых содержится описание j-ой дороги в формате aj bj cj, где aj, bj – концы текущей дороги, а cj – цвет этой дороги (маленькая латинская буква). Порядок выводимых дорог не имеет значения, концы дороги можно выводить в произвольном порядке.
3
1 2 a
1 3 b
2 3 ab
1 2 a
1 3 b
2
2 1 a
2 1 a
