Phá đường

View as PDF

Submit solution


Points: 0.32 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

Đấ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.

Input

  • Dòng ~1~: Ba số nguyên ~N~, ~M~, ~Q~. (~1 \leq N~, ~M \leq 10^{5}~, ~1 \leq Q \leq 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á).

Output

  • 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}~.

Sample Input

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

Sample Output

1
2
3

Comments

Please read the guidelines before commenting.



  • -4
    long1305  commented on 14, Sep, 2021, 14:57

    in số vùng liên thông trước khi phá