Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QHROAD - Phá đường

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qhroad


Đấ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 ≤ 105, 1 ≤ Q ≤ M).
  • Dòng thứ i trong M dòng tiếp theo, mỗi dòng chứa 2 số xi, yi với ý nghĩa: con đường thứ i nối 2 thành phố xi và yi.
  • Dòng thứ i trong Q dòng tiếp theo, mỗi dòng chứa số idi 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 idi.

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
Output 2:
3

Được gửi lên bởi:Quan To
Ngày:2012-11-09
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED

hide comments
2016-03-05 10:46:36
dữ ngu

Last edit: 2016-03-05 10:47:18
2013-08-24 09:37:54 dũng
23,44
2013-08-24 07:09:04 Sơn Sì
:( kho that
2013-08-24 07:07:25 Sơn Sì
zzzzz
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.