Tí có một đồ thị vô hướng gồm ~N~ đỉnh và ~M~ cạnh (có thể không liên thông). Tí đang rất hạnh phúc với đồ thị của mình, nhưng mọi việc không đơn giản như thế. Tí đột nhiên nhận ra đồ thị của mình là không ổn định.

Sau một hồi tính toán, Tí thấy rằng đồ thị của mình phải thỏa mãn ~Q~ yêu cầu, mỗi yêu cầu được biểu diễn bằng một cặp số ~(u, v)~, nghĩa là phải tồn tại đường đi giữa hai đỉnh ~(u, v)~ trên đồ thị của Tí. Chỉ khi thỏa mãn tất cả ~Q~ yêu cầu, đồ thị của Tí mới được xem là ổn định.

Tuy nhiên, trong xã hội này, cần cù thì bù siêng năng, chỉ có làm mới có ăn. Để có thể thêm một cạnh ~(u, v)~ vào đồ thị, Tí phải tốn một chi phí là ~u \times v~. Vì Tí là sinh viên cuối tháng (Tí cũng muốn có ăn), nên anh ấy muốn tìm một cách nối để đồ thị của anh ấy là ổn định, sao cho tổng chi phí nối là thấp nhất có thể. Các bạn hãy giúp Tí nhé.

Input

• Dòng đầu tiên nhập vào ba số ~N, M, Q~ ~(1 \leq N, M, Q \leq 2 \times 10^5)~ lần lượt là số đỉnh, số cạnh của đồ thị và số yêu cầu.
• ~M~ dòng tiếp theo, mỗi dòng nhập vào hai số ~u~ và ~v~ ~(1 \leq u, v \leq N)~ thể hiện cho cạnh nối giữa hai đỉnh ~u~ và ~v~.
• ~Q~ dòng cuối cùng, dòng thứ ~j~ nhập vào hai số ~a~ và ~b~ ~(1 \leq a, b \leq N)~ thể hiện cho yêu cầu thứ ~j~.

Output

• In ra kết quả của bài toán trên.

Sample Input

7 4 3
1 2
3 4
5 6
6 7
1 4
4 7
3 5

Sample Output

8

Giải thích test mẫu

Đồ thị trước khi thêm đỉnh

Đồ thị sau khi thêm đỉnh

• Tổng chi phí sau khi thêm đỉnh ~(1, 3)~ và ~(1, 5)~ là ~1 \times 3 + 1 \times 5 = 8~. Đây cũng là chi phí thấp nhất có thể.

Scoring