Поиск

Пожар в стране


Ограничение времени               1 секунда
Ограничение памяти 64Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt

В связи с невероятной жарой и отсутствием осадков, маленькую страну на небольшом острове «Ярз и Ева» охватили ужасные пожары. Благодаря слаженным действиям спасателей все жители страны были эвакуированы на близлежащие планеты.

Спасать же страну остался маленький пожарный робот. Ему удалось потушить все города кроме столицы. Для тушения была истрачена вся жидкость, поэтому страна обречена сгореть.

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

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

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

В первый день горит только столица. Каждый следующий день дополнительно загораются все города, соединенные дорогами с уже горящими.

Если пилот оставляет робота в горящем городе или направляет его в уже горящий город, то робот не выдерживает огня и уничтожается. Попробуйте определить, кто при оптимальном поведении обоих пилотов уплатит штраф за потерянного робота. Учтите, что загоревшись однажды, город продолжает гореть длительное время (большее чем период времени, рассматриваемый в задаче).

Формат ввода

В первой строке задано количество городов n и дорог m в стране (2 ≤ n, m ≤ 1000). В следующих m строках описаны дороги: a, b — номера городов, соединенных дорогами (1 ≤ a ≤ n, 1 ≤ b ≤ n, a ≠ b). Дороги являются двусторонними, между любой парой городов существует не более одной дороги. Между любыми двумя городами существует путь.

Формат вывода

В выходной файл выведите имя пилота, который заплатит штраф при оптимальном поведении обоих пилотов. («Nikolay» — если это Николай, «Vladimir» — если это Владимир)

Пример

Ввод

4 3
1 2
1 3
2 4

Вывод

Vladimir


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