CF59E.Shortest Path

In Ancient Berland there were n cities and m two-way roads of equal length. The cities are numbered with integers from 1 to n inclusively. According to an ancient superstition, if a traveller visits three cities a__i, b__i, c__i in row, without visiting other cities between them, a great disaster awaits him. Overall there are k such city triplets. Each triplet is ordered, which means that, for example, you are allowed to visit the cities in the following order: a__i, c__i, b__i. Vasya wants to get from the city 1 to the city n and not fulfil the superstition. Find out which minimal number of roads he should take. Also you are required to find one of his possible path routes.

在古代贝尔兰，有 $n$ 座城市和 $m$ 条长度相等的双向道路。城市编号为 $1$ 到 $n$（含端点）。根据一项古老迷信，若旅行者连续访问三座城市 $a_i$、$b_i$、$c_i$（中间不经过其他城市），则将遭遇巨大灾难。总共存在 $k$ 个这样的城市三元组。每个三元组是有序的，这意味着例如按 $a_i$、$c_i$、$b_i$ 的顺序访问这些城市是允许的。瓦夏希望从城市 $1$ 出发到达城市 $n$，且不触犯该迷信。请找出他所需经过的最少道路条数，并给出一条满足条件的可行路径。

The first line contains three integers n, m, k (2 ≤ n ≤ 3000, 1 ≤ m ≤ 20000, 0 ≤ k ≤ 105) 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.

第一行包含三个整数 $n$、$m$、$k$（$2 \leq n \leq 3000$，$1 \leq m \leq 20000$，$0 \leq k \leq 10^5$），分别表示城市的数量、道路的数量以及被禁止的三元组的数量。

接下来是 $m$ 行，每行包含两个整数 $x_i$、$y_i$（$1 \leq x_i, y_i \leq n$），描述一条道路。该道路连接编号为 $x_i$ 和 $y_i$ 的两座城市。不存在连接同一座城市的道路，任意两座城市之间至多只有一条道路。

再接下来是 $k$ 行，每行包含三个整数 $a_i$、$b_i$、$c_i$（$1 \leq a_i, b_i, c_i \leq n$），表示一个被禁止的三元组。每个有序三元组至多出现一次。每个三元组中的三座城市互不相同。

城市 $n$ 可能无法通过道路从城市 $1$ 到达。

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.

如果不存在从城市 1 到城市 $n$ 的路径，则输出 $-1$。否则，在第一行输出从城市 1 到城市 $n$ 的最短路径所经过的道路数量 $d$；在第二行输出 $d+1$ 个数——即瓦夏可能走的一条最短路径（该路径应起始于城市 1，终止于城市 $n$）。