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

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

## Comments