Pussycat Sonya is standing on the graph in the node with number 1 and she wants to reach the node number N. It's known that graph consists of N nodes and M undirected edges. Getting through the edge takes 1 unit of time. It's also known that there are K moments of time in which some edges will disappear. Let's consider this process in more detail. Sonya stands in the node number 1 at the moment of time = 0. Moving to any of adjacent nodes through the edge increases time by 1 unit. And once she changed her location all edges that must disappear at that moment of time become unavailable.

What is the minimal time Sonya needs to reach the node number N? If it's impossible print -1.

Input:
The first line of input contains three integers N - the number of nodes, M - the number of edges and K - the number of moments of time in which some edges will disappear.
Each of the next M lines contains a pair of integers Ui and Vi which means that edge number i connects node number Ui and node number Vi. You can assume that between any pair of nodes there's no more than one connecting edge and there's no edge connecting some node to itself.
Then K lines follow. Each of these lines contains a pair of integers T and X which means that at moment of time T the edge number X will disappear. You can assume that all Xs will be unique.

Output:
Print the minimal time Sonya needs to reach the node number N, if it's impossible print -1.

Constraints:
1 ≤ N ≤ 10^5
0 ≤ K ≤ M ≤ min((N · (N - 1)) / 2, 10^5)
1 ≤ Ui, Vi ≤ N
1 ≤ T ≤ 10^9
1 ≤ X ≤ M

SAMPLE INPUT
5 5 1
1 2
1 3
2 5
3 4
4 5
1 3

SAMPLE OUTPUT
3

见题面

见题面