eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Найдовший шлях

Найдовший шлях

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

У заданому орієнтовному графі знайдіть найдовший шлях такий, що кожна вершина графа зустрічається у ньому не більше одного разу.

Вхідні дані

У першому рядку задано два цілих числа n та m (1n22, 0m1000). У наступних m рядках задано ребра графа у форматі u[i] v[i] - номери початкової і кінцевої вершин ребра i, відповідно. Граф може містити петлі і кратні ребра.

Вихідні дані

У першому рядку виведіть довжину шуканого шляху l. У другому рядку виведіть l + 1 число - вершини шляху у порядку обходу. Якщо оптимальних відповідей декілька, можна вивести довільну з них.

Приклад

Вхідні дані #1
3 3
1 2
2 3
3 1
Вихідні дані #1
2
1 2 3
Вхідні дані #2
4 6
1 2
2 1
2 3
2 4
3 2
4 2
Вихідні дані #2
2
1 2 3
Вхідні дані #3
5 3
3 2
2 2
1 5
Вихідні дані #3
1
3 2
Автор Сергій Копеліович
Джерело 2011 Зимова Школа, Харків, День 5