暂无测试数据。

题目描述

给定一个包含 \(N\) 个点，\(M\) 条边的无向图，每条边的边权均为 1。
再给定 \(K\) 个三元组 \((A,B,C)\)，
表示从 \(A\) 点走到 \(B\) 点后不能往 \(C\) 点走(即路径中不能出现连续三个点为ABC)。
注意三元组是有序的，如可以从 \(B\) 点走到 \(A\) 点再走到 \(C\) 点。
现在你要在 \(K\) 个三元组的限制下，
找出 \(1\) 号点到 \(N\) 号点的最短路径。

输入

第一行，有三个数 \(N,M,K\)，意义如题目所述。
接下来 \(M\) 行，每行两个数 \(A,B\)，表示 A,B 间有一条边。
再下面 \(K\) 行，每行三个数 \((A,B,C)\) 描述一个三元组。

输出

输出一个数\(S\)，表示最短路径长度。

样例输入

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

样例输出

4

数据范围限制

对于 \(40\%\) 的数据满足 \(N \leq 10\),\(M \leq 20\),\(K \leq 5\)。
对于 \(100\%\) 的数据满足 \(N \leq 3000\),\(M \leq 2 \times 10^4\),\(K \leq 10^5\)。

来源

基础篇补充6.7