Học sử

Xem dạng PDF

Gửi bài giải


Điểm: 0,82 (OI)
Giới hạn thời gian: 0.6s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Pirate rất thích học môn Sử. Một hôm, anh tình cờ tìm được một cuốn sách sử địa phương. Chăm chú đọc, Pirate phát hiện ra rằng quần đảo của mình có một lịch sử rất huy hoàng ...

Vào năm XYZ trước Công Nguyên, quần đảo của Pirate được gồm nhiều hòn đảo nhỏ ở gần nhau. Khi kinh tế của mỗi hòn đảo ngày càng phát triển dẫn đến nhu cầu các hòn đảo phải trao đổi hàng hóa. Vậy là những cây cầu dừa được xây dựng ở một số cặp hòn đảo để có thể được từ đảo này sang đảo kia và ngược lại. Theo quy luật tự nhiên, khi có trao đổi hàng hóa nhảy vọt sẽ dẫn đến nhu cầu liên kết và mở rộng thị trường. Vì vậy, các hòn đảo dần tập hợp lại và mở ra một thời đại mới, thời đại của các quốc gia trên biển.

Một quốc gia là tập hợp của một số hòn đảo, mỗi hòn đảo chỉ thuộc vào một quốc gia. Nhận thấy rằng các cây cầu dừa rất mỏng manh nhưng lại vô cùng trọng yếu, các hòn đảo chỉ liên kết lại thành một quốc gia khi và chỉ khi chúng vẫn đi được đến nhau nếu có bất cứ một cây cầu dừa nào nối hai hòn đảo thành viên không sử dụng được.

Sự phân chia này dẫn đến việc các hòn đảo có nền kinh tế tương đương có điều kiện vô cùng thuận lợi để phát triển. Hệ quả tất yếu là sự phân hóa giữa các nước quốc gia. Một số quốc gia trở nên hùng mạnh hơn hẳn các quốc gia khác. Ta gọi đó là các siêu cường.

Sách sử ghi lại rằng một quốc gia hoặc là một siêu cường, hoặc có cầu dừa nối trực tiếp tới một siêu cường. Hơn nữa, sách có lưu ý rằng số siêu cường là ít nhất có thể nhưng không có ghi chép nào khác nữa về chúng. Dựa vào sơ đồ các cây cầu dừa của khác hòn đảo khi xưa, Pirate muốn xác định xem vào thuở sơ khai, quần đảo có bao nhiêu siêu cường. Bạn hãy giúp anh ấy nhé.

Input

  • Dòng ~1~: Hai số nguyên ~N~ - số hòn đảo, ~M~ - số lượng các cây cầu dừa.
  • ~M~ dòng tiếp theo: Mỗi dòng chứa hai số nguyên, mô tả các cặp hòn đảo có cầu dừa nối với nhau.

Output

  • Một số nguyên duy nhất là số siêu cường.

Giới hạn

  • ~1 \leq N~, ~M \leq 10^{5}~.
  • ~30\%~ số test có ~1 \leq N~, ~M \leq 20~.
  • Giữa một cặp hòn đảo chỉ có tối đa một cây cầu dừa nối chúng.

Sample Input 1

6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4

Sample Output 1

1

Sample Input 2

15 19
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
10 11
11 12
12 10
13 14
14 15
15 13
1 4
1 7
1 10
1 13

Sample Output 2

1

Note

  • SAMPLE 1:

    có hai quốc gia là ~(1~, ~2~, ~3)~ và ~(4~, ~5~, ~6)~. Chúng có đường nối trực tiếp với nhau, vì vậy siêu cường có thể là một trong hai.

  • SAMPLE 2:

    có năm quốc gia là ~(1~, ~2~, ~3)~, ~(4~, ~5~, ~6)~, ~(7~, ~8~, ~9)~, ~(10~, ~11~, ~12)~, ~(13~, ~14~, ~15)~. Để số siêu cường là ít nhất thì chỉ có thể có một siêu cường là ~(1~, ~2~, ~3)~ vì mọi quốc gia khác điều có cầu dừa nối trực tiếp đến nó.


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    Leito  đã bình luận lúc 5, Tháng 2, 2024, 10:44

    Cho em hỏi là bài này có trường hợp đa đồ thị không ạ?


  • -10
    thefrog  đã bình luận lúc 5, Tháng 2, 2022, 8:54

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -7
      alex_ngoc_nghech  đã bình luận lúc 8, Tháng 2, 2022, 1:19

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -8
    thefrog  đã bình luận lúc 5, Tháng 2, 2022, 2:19

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -9
    thefrog  đã bình luận lúc 4, Tháng 2, 2022, 16:04

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -11
    thefrog  đã bình luận lúc 3, Tháng 2, 2022, 10:41

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -1
    WuTan  đã bình luận lúc 4, Tháng 6, 2021, 19:05

    Dạ cho em hỏi tại sao khi em khai báo danh sách kề đồ thị bằng cách :

    vector < vector < int > > adj;

    adj.resize(n + 1);

    thì bị RTE 3 test

    còn nếu em khai báo vector < int > adj[int(1e5) + 1)] thì bình thường ạ

    em cảm ơn <3


    • -5
      hdh_  đã bình luận lúc 5, Tháng 2, 2022, 16:28

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -2
      thefrog  đã bình luận lúc 28, Tháng 1, 2022, 16:01

      làm sao để xác định siêu cường lớn nhất ạ


    • 9
      leduykhongngu  đã bình luận lúc 5, Tháng 6, 2021, 3:41

      Ồ do test chúng mình bị sai bạn nhé, có những đỉnh lớn hơn n. Mình đã sinh lại test và chấm lại các submission rồi nhé :3


      • -16
        Airi  đã bình luận lúc 6, Tháng 6, 2021, 7:04

        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.