## WOSS Dual Olympiad 2023 Team Round P3: Choosing Edges

View as PDF

Points: 12
Time limit: 2.0s
Memory limit: 1G

Authors:
Problem type

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.

#### 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

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

2

#### Sample Input 2

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

4

#### Sample Input 3

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

#### Sample Output 3

3