Пожежа в країні
У зв'язку з неймовірною спекою та відсутністю опадів, маленька країна на острові "Ярз і Єва" постраждала від жахливих пожеж. Завдяки злагодженим діям рятувальників усі жителі були евакуйовані на найближчі планети.
Залишився лише маленький пожежний робот, який зміг загасити всі міста, окрім столиці. Вся рідина для гасіння була використана, тому країна приречена згоріти.
Полум'я поширюється дуже швидко: щодня вогонь охоплює всі міста, з'єднані дорогами з уже палаючими містами. Робот не може більше гасити вогонь, тому єдине, що йому залишається, — це тікати. Швидкість робота дорівнює швидкості вогню, тому за один день він може переміститися в сусіднє місто.
Роботом по черзі керують два пілоти, Микола і Володимир, які знаходяться на природному супутнику Землі. Незважаючи на те, що робота вже не врятувати і користі від нього немає, пілоти дуже зацікавлені, щоб він був знищений не в їхню зміну. За втрату робота передбачено значне вирахування із заробітної плати.
У перший день робот знаходиться в столиці (місті номер 1). Микола керує роботом у перший день і може направити його в будь-яке місто, з'єднане з 1. Далі пілоти чергуються. Таким чином, кожного дня робот може переміститися в будь-яке сусіднє місто.
У перший день горить тільки столиця. Кожного наступного дня загоряються всі міста, з'єднані дорогами з уже палаючими.
Якщо пілот залишає робота в палаючому місті або направляє його в уже палаюче місто, робот не витримує вогню і знищується. Визначте, хто при оптимальній поведінці обох пілотів заплатить штраф за втраченого робота. Врахуйте, що загорівшись одного разу, місто продовжує горіти тривалий час (більший, ніж період часу, розглянутий у задачі).
Вхідні дані
У першому рядку задано кількість міст n і доріг m у країні (2 ≤ n, m ≤ 1000).
У наступних m рядках описані дороги: a, b - номери міст, з'єднаних дорогами (1 ≤ a ≤ n, 1 ≤ b ≤ n, a ≠ b). Дороги є двосторонніми, між будь-якою парою міст існує не більше однієї дороги. Між будь-якими двома містами існує шлях.
Вихідні дані
У вихідний файл виведіть ім'я пілота, який заплатить штраф при оптимальній поведінці обох пілотів ("Nikolay" - якщо це Микола, "Vladimir" - якщо це Володимир).