• Война "роз"
  WAR OF "ROSES"

Описание
В истории гражданская война 1455-1485 гг. в Англии получила название Войны Алой и Белой роз, или Войны Ланкастеров и Йорков. В то время на английском троне восседал уродливый горбун из династии Йорков, многочисленные злодеяния которого описаны Шекспиром в трагедии "Ричард III". В то же самое время молодой граф Ричмонд, последний из династии Ланкастеров, решил покарать злодея и восстановить историческую справедливость. Он долго водил свой флот вдоль английских берегов, выбирая наиболее удобное место высадки. Ричмонд высадился в Уэльсе как король Генрих VII, и на его сторону начали переходить феодалы, которые еще недавно клялись в верности Белой розе.

Представим, что на момент высадки Англия состояла из N (1<V<50) графств, причем все они признавали власть Белой розы. Примем, что если Ричмонд высаживается в одном из графств, оно в тот же день переходит на его сторону. Каждый следующий день на сторону Ричмонда переходят все графства, которые непосредственно граничат с уже захваченной им территорией.

Задача
Итак, перед Ричмондом лежит карта Англии и он решает, в каком графстве высадиться, чтобы захватить всю Англию за кратчайшее время.

Технические требования:

Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT

Входные данные
Графства пронумерованы от 1 до N. В каждой строке входного файла через пробел записаны два номера, означающие, что соответствующие графства граничат друг с другом. Связность карты гарантируется. Данные заканчиваются строкой с двумя нулями, которая не подлежит обработке.

Выходные данные
В файл выходных данных следует записать одно число: наименьшее количество дней (включая день высадки), за которые можно захватить все графства Англии.

Примеры:

INPUT.TXT
1  2
3  4
2  3
4  5
0  0

OUTPUT.TXT
3