Shortest Path in Graph with Forbidden Turns

You are given an undirected graph with N vertices and M edges. Each edge has a weight of \(1\). Additionally, you are given K ordered triples \((A,B,C)\) representing a restriction: if you traverse from vertex A to vertex B, you are not allowed to immediately proceed to vertex C. Note that the triple is ordered; for example, it might be possible to go from B to A and then to C, but not from A to B and then to C.

Your task is to find any shortest path from vertex 1 to vertex N that obeys all the given restrictions and output the corresponding sequence of vertices. There is a check mechanism that verifies whether your output path is valid.

inputFormat

The first line contains three integers \(N\), \(M\), and \(K\), representing the number of vertices, the number of edges, and the number of restrictions respectively.

The next \(M\) lines each contain two integers \(u\) and \(v\) (1-based), indicating that there is an undirected edge between vertices \(u\) and \(v\).

The following \(K\) lines each contain three integers \(A\), \(B\), and \(C\), representing that if you travel from vertex \(A\) to vertex \(B\), you are forbidden from going directly to vertex \(C\).

outputFormat

If there exists a valid path from vertex 1 to vertex \(N\), output any one of the shortest valid paths as a sequence of vertex numbers separated by spaces. If no valid path exists, output -1.

sample

4 4 1
1 2
2 3
3 4
1 4
1 2 3

1 4