Старий Зеник не має, чим зайнятись
Обмеження: 2 сек., 256 МіБ
Зеник дуже любить бавитися з «lego», але його батьки бояться, що він може його проковтнути, тому дають йому натомість гратися тільки з трубами. Але й це, виявляється, не зовсім безпечна забавка.
Зеник знає, що в Марічки є \(n\) різних кліток (пронумерованих від 1 до \(n\)), у яких вона тримає свого домашнього улюбленця — чорну водяну змію. Хлопчина взяв і поз’єднував трубами деякі із цих кліток таким чином, що змія може ними пересуватися між клітками. Згідно зі стародавнім передбаченням кінець світу настане, коли чорна водяна змія двічі побуває в одній і тій же клітці. Але проблема от у чому — змія кожною трубою може проповзти тільки один раз.
Тоді запитання до вас, школярі: «Який найменший номер клітки, у яку змія зможе повернутись, якщо кожною з труб повзтиме не більше одного разу?».
Зеник обіцяє, що між кожною парою кліток буде не більше ніж одна труба, і що труба не з’єднує клітку саму із собою.
Вхідні дані
Перший рядок містить два цілих числа \(n\) і \(m\) — кількість кліток та кількість труб, які є в цій апокаліптичній конструкції.
Далі в \(m\) рядках дано по два натуральних числа \(a_i\) та \(b_i\), які означають, що \(і\)-ою трубою Зеник з’єднав клітки з номерами \(a_i\) та \(b_i\).
Вихідні дані
У єдиному рядку виведіть ціле число — найменший номер клітки, з якої
може починати свою подорож змія і потім повернутися в ту ж клітку, при
цьому проповзши кожною з труб не більше одного разу. Якщо такої клітки
немає, то виведіть -1
.
Обмеження
\(1 \le n \le 100\),
\(1 \le m \le 10^3\),
\(1 \le a_i, b_i \le n\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 4 1 4 4 2 4 3 3 2 | 2 |
Примітки
Ну…Для тих, хто досі не зрозумів — потрібно знайти найменший номер клітки, яка є в циклі.
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|