You have an unweighted directed graph with
nodes and
edges. The
th edge goes from node
to
. You also have
other directed edges which are not currently in the graph. The
th edge in this set has a color
and goes from node
to
. You may add either
or
edges from this set onto the graph. If you add
edges, they must have different colors. Determine the minimum distance from node
to node
after adding the optimal edges, or output -1
if node
is still unreachable.
Constraints




Input Specification
The first line of input contains
space-separated integers
,
, and
.
The next
lines each contain
space-separated integers,
and
.
The next
lines each contain
space-separated integers,
,
, and
.
Output Specification
Output a single integer, the minimum distance from node
to node
after adding the optimal
edges.
If it is impossible to reach node
from node
, output -1
.
Sample Input
Copy
7 7 5
1 2
2 3
1 4
4 5
3 5
6 5
7 6
1 5 1
3 7 3
3 4 3
1 3 2
5 7 1
Sample Output
Copy
2
Sample Input 2
Copy
9 4 7
1 2
2 3
3 4
4 9
1 8 1
8 9 1
1 7 1
7 9 1
1 6 1
6 5 2
5 9 3
Sample Output 2
Copy
4
Sample Input 3
Copy
4 2 2
1 3
3 2
1 2 1
2 4 1
Sample Output 3
Copy
3
Comments