Shortest Path

Description:

Input:

The first line contains three integers n, m, k (2 ≤ n ≤ 3000, 1 ≤ m ≤ 20000, 0 ≤ k ≤ 10⁵) which are the number of cities, the number of roads and the number of the forbidden triplets correspondingly.

Then follow m lines each containing two integers x_i, y_i (1 ≤ x_i, y_i ≤ n) which are the road descriptions. The road is described by the numbers of the cities it joins. No road joins a city with itself, there cannot be more than one road between a pair of cities.

Then follow k lines each containing three integers a_i, b_i, c_i (1 ≤ a_i, b_i, c_i ≤ n) which are the forbidden triplets. Each ordered triplet is listed mo more than one time. All three cities in each triplet are distinct.

City n can be unreachable from city 1 by roads.

Output:

If there are no path from 1 to n print -1. Otherwise on the first line print the number of roads d along the shortest path from the city 1 to the city n. On the second line print d + 1 numbers — any of the possible shortest paths for Vasya. The path should start in the city 1 and end in the city n.

Sample Input:

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

Sample Output:

2
1 3 4

Sample Input:

3 1 0
1 2

Sample Output:

-1

Sample Input:

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

Sample Output:

4
1 3 2 3 4