Граф Калиостро, колеся по необъятным просторам Российской
империи, озабочен тем, удастся ли ему проехать в карете, предположим, из
Вышнего Волочка в Тобольск.
Граф уже знает, что в России дорогой называют то место, где
кто-либо когда-либо проехал или хотя бы собирался проехать. Такая трактовка его
не устраивает, он собирается ездить только по официальным почтовым трактам.
И вот сидит граф на постоялом дворе, листая справочник
«Почтовые тракты Российской империи» за 1780 год. Города в нём пронумерованы от
1 до N. Далее следует
список из M дорог, про каждую известен номер начального Bi и конечного Ei города, i=1..N. Все дороги преодолимы в
обоих направлениях, но в справочник внесены по 1 разу.
Итак, разработайте программу, определяющую, можно ли
проехать по почтовым трактам из города с номером В в город с номером Е, и если
да – через какое наименьшее количество трактов.
Ввод: в первой
строке натуральных 4 числа – N,
M, В, Е, N<=100, M<=1000, значения гарантированно
корректны; далее M строк, описывающих дороги, каждая содержит номера начального
и конечного городов.
Вывод: YES и через пробел число
дорог или NO.
Для отправки решений необходимо