Problems
The longest path
The longest path
In an oriented graph find the longest path such that each vertex of the graph occurs no more than once in it.
Input
First line contains two integers n and m (1 ≤ n ≤ 22, 0 ≤ m ≤ 1000). Each of the next m lines contains the edges of the graph in format ui vi
- the numbers of starting and ending vrtices of the edge i. Graph can contain loops and multiedges.
Output
In the first line, output the length of the longest path l. In the second line print l + 1 number - the vertices of the path in the order of traversal. If there are several optimal answers, output any of them.
Input example #1
3 3 1 2 2 3 3 1
Output example #1
2 1 2 3
Input example #2
4 6 1 2 2 1 2 3 2 4 3 2 4 2
Output example #2
2 1 2 3
Input example #3
5 3 3 2 2 2 1 5
Output example #3
1 3 2