CSES - Network Breakdown | Sự cố Mạng lưới

Xem PDF
Tác giả:
Elektrikar
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, Perl, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Swift
Điểm: 2000 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Mạng lưới của Syrjälä có \(n\) máy tính và \(m\) kết nối giữa chúng. Mạng lưới gồm các thành phần các máy tính có thể gửi tin nhắn cho nhau.

Không ai ở Syrjälä biết cách mạng lưới hoạt động. Vì lý do này, nếu một kết nối gặp sự cố, sẽ không ai sửa nó. Trong tình huống này, một thành phần có thể bị chia thành hai thành phần.

Nhiệm vụ của bạn là tính số lượng thành phần sau mỗi sự cố kết nối.

Input

Dòng đầu tiên là ba số nguyên \(n, m\) và \(k\) : số lượng máy tính, kết nối và sự cố. Các máy tính được đánh số \(1,2,...,n\).

Tiếp theo là \(m\) dòng mô tả các kết nối. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) : có một kết nối giữa hai máy \(a\) và \(b\). Mỗi kết nối là giữa hai máy tính khác nhau và có nhiều nhất một kết nối giữa hai máy.

Cuối cùng là \(k\) dòng mô tả các sự cố. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) : kết nối giữa hai máy \(a\) và \(b\) gặp sự cố.

Output

Sau mỗi sự cố, in ra số lượng thành phần.

Giới hạn

  • \(1 \le n \le 10^5\)
  • \(1 \le m \le 2 \cdot 10^5\)
  • \(1 \le k \le m\)
  • \(1 \le a,b \le n\)

Ví dụ

Input

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

Output

2 2 3

Bình luận


  • -2
    vanphukhang_0604    11:36 p.m. 14 Tháng 8, 2023 ← chỉnh sửa 3

    CSES - Network Breakdown | Sự cố Mạng lưới

    Mạng lưới của Syrjälä có \(n\) máy tính và \(m\) kết nối giữa chúng. Mạng lưới gồm các thành phần, mỗi thành phần gồm các máy tính có thể gửi tin nhắn cho nhau.

    Không ai ở Syrjälä biết cách mạng lưới hoạt động. Vì vậy, sẽ không có ai sửa một kết nối gặp sự cố. Trong tình huống này, một thành phần có thể bị chia thành hai thành phần.

    Nhiệm vụ của bạn là tính số lượng thành phần sau mỗi sự cố kết nối.

    Input

    • Dòng đầu tiên chứa ba số nguyên \(n \ (1 \leq n \leq 10^5)\), \(m \ (1 \leq m \leq 2 \cdot 10^5)\) và \(k \ (1 \leq k \leq m)\), lần lượt là số máy tính, số kết nối và số sự cố. Các máy tính được đánh số \(1, 2, \ldots, n\).
    • \(m\) dòng tiếp theo mô tả các kết nối, mỗi dòng chứa hai số nguyên \(a\) và \(b \ (1 \leq a, b \leq n)\), ứng với một kết nối giữa máy tính thứ \(a\) và \(b\).
    • \(k\) dòng cuối cùng mô tả các sự cố, mỗi dòng chứa hai số nguyên \(a\) và \(b\), ứng với kết nối giữa máy tính thứ \(a\) và \(b\) gặp sự cố.

    Output

    • In ra số lượng thành phần sau mỗi sự cố.

    Example

    Test 1

    Input 
    5 5 3
1 2
1 3
2 3
3 4
4 5
3 4
2 3
4 5
    Output 
    2 2 3
    1 phản hồi