Cho đồ thị vô hướng, không có trọng số gồm ~N~ đỉnh và ~M~ cạnh.

Có ~K~ bộ ba đỉnh ~(a, b, c)~ bị cấm, nghĩa là không thể đi theo lộ trình ~a \rightarrow b \rightarrow c~; nói cách khác, nếu đi từ ~a~ đến ~b~ thì không thể đi tiếp sang ~c~.

Yêu cầu: Hãy tìm đường đi ngắn nhất từ đỉnh ~1~ đến đỉnh ~N~ sao cho không đi qua bất kỳ bộ ba cấm nào.

Input

• Dòng đầu tiên chứa ba số nguyên ~N, M, K~ ~(2 \le N \le 3000; 1 \le M \le 2 \times 10^4; 0 \le K \le 10^5)~ lần lượt là số đỉnh, số cạnh của đồ thị và số bộ ba đỉnh bị cấm;

• Trong ~M~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~x~ và ~y~ biểu thị một cạnh vô hướng nối giữa hai đỉnh ~x~ và đỉnh ~y~ ~(1 \le x, y \le N; x \ne y)~. Đồ thị có thể có nhiều hơn một cạnh nối giữa hai đỉnh;

• Trong ~K~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a, b, c~ ~(1 \le a, b, c \le N; a \ne b, b \ne c)~ mô tả một lộ trình ~a \rightarrow b \rightarrow c~ bị cấm. Dữ liệu đảm bảo các bộ ba bị cấm đều phân biệt.

Các số trên cùng một dòng cách nhau ít nhất một dấu cách.

Output

Ghi ra một số nguyên là độ dài đường đi ngắn nhất tìm được. Nếu không tìm được đường đi hợp lệ, in ra ~-1~.

Scoring

Sample Input 1

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

Sample Output 1

4

Notes

Đường đi ngắn nhất có độ dài ~4~ với lộ trình ~1 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 4~.