Школа Зебры
(Время: 3 сек. Память: 256 Мб Сложность: 62%)
Морозным зимним вечером Геральт, Весемир и Сигизмунд собрались в Каэр-Морхене в дружеской кампании. Сигизмунд недавно вернулся из Зеррикании и развлекал приятелей историями об этой жаркой стране. Весемира так впечатлили рассказы, что он захотел создать ведьмачью Школу Зебры.
Сигизмунд припомнил озеро, расположенное неподалёку, на котором находятся n островов, соединённых m мостами, и предложил испытание о нахождении кратчайшего пути от одного острова до другого.
Весемир продолжил мысль: «Мы покрасим каждый мост в белый или чёрный цвет, и нужно будет найти путь от острова 1 до острова
n. При этом, передвигаясь по островам, если последний переход был по мосту цвета c, то следующий переход должен быть по мосту другого цвета, а иначе за переход начисляется штраф в 1 щелбан».
Весемир так загорелся идеей, что уже на следующее утро Геральт таскался по озеру и красил мосты, а Весемир до вечера уехал по делам. К вечеру Геральт выполнил указание, но обеспокоился за лбы будущих учеников, а существует ли хоть один путь от острова
1 до острова n, в котором чередуются цвета мостов, по которым совершаются переходы?
Чтобы не расстроить Весемира, Геральту до его приезда необходима ваша помощь. Определите есть ли путь, за который не начислится штраф и если да, то каково минимальное число мостов в таком пути. Если такого пути нет, то определите за какой минимальный штраф можно пройти от острова 1 до острова n.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n и m (2 ≤ n ≤ 105; 1 ≤ m ≤ 2×105).
В следующих m строках содержатся тройки целых чисел v, t и c (1 ≤ v, t ≤ n; v≠t; 0 ≤ c ≤ 1), означающих, что острова с номерами
v и t соединены мостом цвета c (0 — чёрный, 1 — белый).
Гарантируется, что от 1 до n можно добраться по существующим мостам.
Выходные данные
В выходной файл OUTPUT.TXT выведите «YES» и количество мостов в пути, если существует чередующийся путь от 1 до n. Если такого пути не существует, то выведите «NO», а следом минимальное количество штрафа, за которое можно пройти.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 5
1 2 1
2 3 0
3 5 1
1 4 0
4 5 0 | YES 3 |
| 2 | 7 7
1 2 0
2 3 1
3 4 1
4 7 1
2 5 1
5 6 0
6 4 1 | NO 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
