В Берляндии n городов, столица находится в городе s, а историческая родина Президента — в городе t (s ≠ t). Города соединены односторонними дорогами, время проезда по каждой из дорог — целое положительное число.
Раз в год Президент посещает свою историческую родину t, для чего его кортеж проезжает по некоторому пути из s в t (обратно он всегда возвращается на личном самолете). Так как Президент — очень занятой человек, то он всегда выбирает путь из s в t, по которому он проедет быстрее всего.
Министерство дорог и путей сообщения хочет узнать для каждой дороги: обязательно ли проедет по ней Президент во время своего путешествия, и если нет, то возможно ли её починить так, чтобы она в любом случае входила в кратчайший путь из столицы в историческую родину Президента. Очевидно, что дорогу невозможно починить так, чтобы время проезда по ней стало меньше единицы. Министерство Берляндии, как и любое другое, заинтересовано в сохранении бюджета, поэтому оно хочет узнать минимальную стоимость починки дороги. Также оно очень любит точность, поэтому ремонтирует дороги так, что время проезда по ним всегда остаётся целым числом.
Выходные данные
Выведите m строк. В i-й строке должна содержаться информация об i-й дороге (дороги нумеруются с единицы в порядке следования во входных данных).
Если президент в любом случае проедет по ней во время своего путешествия, строка должна содержать единственное слово «YES» (без кавычек).
Иначе если i-ю дорогу возможно починить так, чтобы время проезда по ней осталось положительным, и президент в любом случае выбрал бы её для своего путешествия, выведите через пробел слово «CAN» (без кавычек) и минимальную стоимость ремонта.
Если же нельзя починить дорогу так, чтобы по ней в обязательном порядке проехал президент, выведите «NO» (без кавычек).
Примечание
Стоимостью починки дороги называется разность между временем проезда по ней до и после починки.
В первом тесте из условия президент исходно может выбрать один из двух маршрутов для своей поездки: 1 → 2 → 4 → 5 → 6 либо 1 → 2 → 3 → 5 → 6.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 7 1 6
1 2 2
1 3 10
2 3 7
2 4 8
3 5 3
4 5 2
5 6 1
|
YES
CAN 2
CAN 1
CAN 1
CAN 1
CAN 1
YES
|
|
2
|
3 3 1 3
1 2 10
2 3 10
1 3 100
|
YES
YES
CAN 81
|
|
3
|
2 2 1 2
1 2 1
1 2 2
|
YES
NO
|