Giải bài trực tuyến

Đất nước nọ có N thành phố và M con đường 2 chiều, mỗi con đường nối 2 thành phố. Chú ý là giữa hai thành phố có thể có nhiều con đường khác nhau nối giữa chúng, và cũng có những con đường nối 1 thành phố với chính nó (dùng cho du lịch chẳng hạn, đi loanh quanh chơi rồi trở về thành phố).

Một nhóm các thành phố được gọi là một vùng liên thông nếu:

• Bất kì 2 thành phố nào trong nhóm cũng đi đến được với nhau
• Không thể thêm bất kì một thành phố nào khác vào nhóm

Một ngày, đất nước bị giặc ngoại xâm đến xâm lược. Địch rất đông và nguy hiểm, người ta quyết định phá đi Q con đường để làm chậm bước tiến của quân thù.

Có một câu hỏi được đặt ra cho bạn là sau khi phá xong mỗi con đường, số vùng liên thông là bao nhiêu.

Dữ liệu

• Dòng 1: Ba số nguyên N, M, Q. (1 ≤ N, M ≤ 10⁵, 1 ≤ Q ≤ M).
• Dòng thứ i trong M dòng tiếp theo, mỗi dòng chứa 2 số x_i, y_i với ý nghĩa: con đường thứ i nối 2 thành phố x_i và y_i.
• Dòng thứ i trong Q dòng tiếp theo, mỗi dòng chứa số id_i là số hiệu của con đường bị phá. (Dữ liệu đảm bào là không có chuyện phá lại con đường đã phá).

Kết quả

• Gồm Q dòng, dòng thứ i trong Q dòng này là số vùng liên thông sau khi phá con đường id_i.

Ví dụ

Input 1:
4 4 3
1 2
2 3
1 3
3 4
2
4
3

Output 1:
1
2
3

Input 2:
3 1 1
1 2
1 

Output 2:
3