Hamiltonian Path in DAG solved by 402

Problem

A Hamiltonian path is a path in a graph that visits each vertex exactly once. Checking whether a graph contains a Hamiltonian path is a well-known hard problem. At the same time it is easy to perform such a check if a given graph is a DAG.

Given: A positive integer $k \le 20$ and $k$ simple directed acyclic graphs in the edge list format with at most $10^3$ vertices each.

Return: For each graph, if it contains a Hamiltonian path output "1" followed by a Hamiltonian path (i.e., a list of vertices), otherwise output "-1".

Sample Dataset

2

3 3
1 2
2 3
1 3

4 3
4 3
3 2
4 1

Sample Output

1 1 2 3
-1