Tại quần đảo ZXY có N hòn đảo, ban đầu một đảo có cầu nối với nhau. Để thuận tiện cho các phương tiện đi lại, ban quản lý lên kế hoạch xây K cầu để từ một đảo ta có thể đi đến các đảo còn lại trong quần đảo bằng đường đi trực tiếp hoặc đi gián tiếp qua các đảo khác. Ban quản lý nhận thấy rằng: có thể không nhất thiết phải xây hết các cầu theo trình tự trong kế hoạch DFSBRG2đưa ra mà vẫn đảm bảo giao thông đi lại giữa các đảo. Cho kế hoạch có K cầu cần xây mới theo thứ tự đầu vào. Hãy cho biết, ban quản lý cần xây ít nhất bao nhiêu cầu mà vẫn đảm bảo giao thông đi lại giữa các đảo. Dữ liệu đảm bảo có nghiệm.

Dữ liệu:

• Dòng 1: Ghi số nguyên N, M và K (N, M, K ≤ 3000).
• M dòng tiếp theo, mỗi dòng ghi số nguyên dương u và v thể hiện đã có cầu nối đảo u và đảo v (u, v ≤ N).
• K dòng tiếp theo, mỗi dòng ghi số nguyên dương u và v thể hiện sẽ xây cầu nối đảo u và đảo v (u, v ≤ N).

Kết quả: Ghi ra số cầu ít nhất cần xây thêm.

Ví dụ:

INTPUT

12 7 6
1 2
2 5
2 6
6 10
3 4
9 11
9 12
6 7
7 8
3 8
3 9
4 10
3 10

OUTPUT

4