Однажды юный хакер Шалдыга Севин решил совершить дерзкое преступление - сменить имя своего друга Максима Никитина на сильвере, пока тот был в ЛКШ Зима (Ливневая Коробка Шредингера), чтобы Наталья Владимировна поставила ему двойку. Для этого Шалдыга решил заразить вирусом базу данных сильвера.
Однако юный хакер осознал одну проблему - он не знает, на каком именно компьютере лицея она хранится. Шалдыга не стал долго думать над этой проблемой и решил заразить все компьютеры в лицее (для надежности). Вирус работает так: раз в день он заражает все компьютеры, связанные с зараженными напрямую. Первый компьютер Шалдыге придется заразить лично, потому он может выбрать любой.
Хакер хочет узнать минимальное количество дней, которое понадобится для того, чтобы заразить все компьютеры лицея. Однако выяснилась еще одна проблема - эта задача легко решается с помощью БФСа, но написать его меньше чем за 15 дней невозможно, а Хакеру еще нужно сделать 200 номеров по математике. Поэтому Шалдыга попросил Вас сделать невозможное - написать программу, отвечающую на его вопрос, за время этого контеста.
Входные данные
В первой строке на вход подаются два числа N и M - количество компьютеров в лицее и соединений между ними соответственно. 1 <= N, M <= 100
В следущих M строках Вам даются описания соединений между компьютерами, а именно 2 чила U и V, которые означают, что компьютеры U и V соединены.
Выходные данные
Выведите ответ на вопрос Шалдыги
|
Ввод |
Вывод |
|
6 9
1 2
1 3
2 4
2 6
3 4
3 5
4 5
4 6
5 6
|
2 |
(с) Григорьев Е., 2017