Замечательные дороги
(Время: 1 сек. Память: 16 Мб Сложность: 62%)
В одной замечательной стране живут замечательные люди. По исследованиям замечательного правительства, большинство граждан на выходных садятся в машину, выбирают циклический маршрут между некоторыми городами и деревнями без повторяющихся населенных пунктов и катаются по этому маршруту, пока не надоест. Некоторые, правда, катаются по своему городу и никуда не выезжают.
Так как правительство заботится о своих гражданах, оно хочет сделать их выходные максимально красочными. По этой причине недавно было принято решение покрасить каждую дорогу между населенными пунктами в какой-нибудь цвет. Причем так, чтобы ни на каком "выходном" маршруте не было дорог одинакового цвета. Но так как цветов могло понадобиться довольно много, правительство решило минимизировать количество различных цветов. Вам предстоит помочь этому замечательному государству в осуществлении его планов.
Входные данные
В первой строке находятся два числа: 1 ≤ n ≤ 50 000 - количество городов и деревень в стране и 1 ≤ m ≤ 100 000 - количество дорог. В m последующих строках находится по два числа – номера населенных пунктов, концов дороги. Ни одна дорога не ведет из города в себя, и между двумя населенными пунктами не может быть более одной дороги. Все дороги двусторонние.
Выходные данные
В первой строке выведите минимальное количество цветов. В последующих m строках выведите по три числа: два конца дороги в любом порядке и ее цвет. Дороги разрешается выводить в произвольном порядке.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 1
1 2 | 1
2 1 1 |
| 2 | 3 2
1 2
2 3 | 1
2 3 1
1 2 1 |
| 3 | 3 3
1 2
2 3
3 1 | 3
1 2 1
3 2 2
3 1 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
