Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Замечательные дороги

(Время: 1 сек. Память: 16 Мб Сложность: 62%)

В одной замечательной стране живут замечательные люди. По исследованиям замечательного правительства, большинство граждан на выходных садятся в машину, выбирают циклический маршрут между некоторыми городами и деревнями без повторяющихся населенных пунктов и катаются по этому маршруту, пока не надоест. Некоторые, правда, катаются по своему городу и никуда не выезжают.

Так как правительство заботится о своих гражданах, оно хочет сделать их выходные максимально красочными. По этой причине недавно было принято решение покрасить каждую дорогу между населенными пунктами в какой-нибудь цвет. Причем так, чтобы ни на каком "выходном" маршруте не было дорог одинакового цвета. Но так как цветов могло понадобиться довольно много, правительство решило минимизировать количество различных цветов. Вам предстоит помочь этому замечательному государству в осуществлении его планов.

Входные данные

В первой строке находятся два числа: 1 ≤ n ≤ 50 000 - количество городов и деревень в стране и 1 ≤ m ≤ 100 000 - количество дорог. В m последующих строках находится по два числа – номера населенных пунктов, концов дороги. Ни одна дорога не ведет из города в себя, и между двумя населенными пунктами не может быть более одной дороги. Все дороги двусторонние.

Выходные данные

В первой строке выведите минимальное количество цветов. В последующих m строках выведите по три числа: два конца дороги в любом порядке и ее цвет. Дороги разрешается выводить в произвольном порядке.

Примеры

INPUT.TXTOUTPUT.TXT
12 1
1 2
1
2 1 1
23 2
1 2
2 3
1
2 3 1
1 2 1
33 3
1 2
2 3
3 1
3
1 2 1
3 2 2
3 1 3

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ