Задачи
Самый длинный путь
Самый длинный путь
В ориентированном графе найдите самый длинный путь такой, что каждая вершина графа встречается в нём не более одного раза.
Входные данные
В первой строке заданы два целых числа n и m (1 ≤ n ≤ 22, 0 ≤ m ≤ 1000). В следующих m строках заданы рёбра графа в формате ui vi
- номера начальной и конечной вершин ребра 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