Đất nước Byteland là một quốc đảo bao gồm N hòn đảo khác nhau. Các đảo được nối với nhau bằng M cây cầu. Dữ liệu đảm bảo rằng chỉ có nhiều nhất một cây cầu giữa hai hòn đảo bất kỳ. Hai đảo được gọi là có thể đi lại được với nhau nếu có tồn tại một cây cầu đi trực tiếp hoặc gián tiếp qua các cây cầu khác.

Các nhà khoa học ở hòn đảo dự đoán trong một tương lai gần sẽ có Q thiên thạch lần lượt rơi xuống hòn đảo. Thiên thạch thứ i sẽ phá huỷ cây cầu e[i]. Nếu thiên thạch rơi vào một cây cầu đã bị phá huỷ trước đó thì xem như thiên thạch đó không phá huỷ thêm bất kỳ cây cầu nào khác.

Để chuẩn bị ứng phó với thiên tai này những người đứng đầu nước Byteland đã họp nhau để lập kế hoạch di tản dân. Họ muốn biết rằng sau khi thiên thạch thứ i rơi, nếu chọn hòn đảo c[i] là nơi tập trung thì còn bao nhiêu hòn đảo mà người dân ở đó có thể di chuyển được tới nơi tập trung.

Dữ liệu

• Dòng đầu tiên gồm ba số nguyên N, M, Q (1 ≤ N ≤ 10^5, 1 ≤ M, Q ≤ 2∗10^5).

• M dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ui và vi biểu diễn cho một cây cầu nối hai hòn đảo ui và vi.

• Q dòng cuối dùng, mỗi dòng gồm 2 số nguyên dương ei và ci biểu diễn cho cây cầu thứ ei sẽ bị thiên thạch rơi trúng và hòn đảo ci được chọn làm nơi tập trung dân.

Kết quả

• Gồm Q dòng, dòng thứ i trả lời cho câu hỏi sau khi i thiên thạch đầu tiên rơi thì còn bao nhiêu hòn đảo có người dân có thể di chuyển tới hòn đảo ci

Sample Input

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

Sample Output

4
2
1

Giải thích

Sau khi quả thiên thách đầu tiên rơi thì cây cầu nối hòn đảo 1 và 4 bị phá huỷ. Tuy nhiên vẫn tồn tại đường đi từ tất cả các đảo tới đảo 1 (1, 2 - 1, 3 - 2 - 1, 4 - 3 - 2 - 1). 
Sau khi thiên thạch thứ hai rơi thì cây cầu nối hòn đảo thứ 2 và 3 bị phá huỷ. Lúc này chỉ có hòn đảo 3 và 4 là có thể đi được tới hòn đảo 3 (3, 4 - 3)
Sau khi thiên thạch cuối cùng rơi thì cây cầu nối hòn đảo thứ 1 và 2 bi phá huỷ. Lúc này chỉ có duy nhất cư dân ở hòn đảo 1 là có thể tập trung ở hòn đảo được chọn.

Ràng buộc

- Subtask 1 (50% số test): N ≤ 1000, M, Q ≤ 2000,
- Subtask 2 (50% số test): Không có ràng buộc gì thêm