QHROAD - Phá đường

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Đấ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 5 , 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

  • Người up: tohuuquan