Truyền tin

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một lớp gồm \(N\) học sinh, mỗi học sinh cho biết những bạn mà học sinh đó có thể liên lạc được (chú ý liên lạc này là liên lạc một chiều: \(u\) có thể gửi tin tới \(v\) nhưng \(v\) thì chưa chắc đã có thể gửi tin tới \(u\)).

Thầy chủ nhiệm đang có một thông tin rất quan trọng cần thông báo tới tất cả các học sinh. Để tiết kiệm thời gian, thầy chỉ nhắn tin tới 1 số học sinh rồi sau đó nhờ các học sinh này nhắn lại cho tất cả các bạn mà các học sinh đó có thể liên lạc được, và cứ lần lượt như thế làm sao cho tất cả các học sinh trong lớp đều nhận được tin.

Hãy tìm một số ít nhất các học sinh mà thầy chủ nhiệm cần nhắn.

Input

  • Dòng đầu là \(N, M\) \((N \leq 800, M \leq 4 \times 10^{5})\) - số lượng học sinh và số lượng liên lạc một chiều.
  • \(M\) dòng tiếp theo mỗi dòng gồm 2 số \(u, v\) cho biết học sinh \(u\) có thể gửi tin tới học sinh \(v\).

Output

  • Gồm 1 dòng ghi số học sinh cần thầy nhắn tin.

Test 1

Input
12 15
1 3
3 6
6 1
6 8
8 12
12 9
9 6
2 4
4 5
5 2
4 6
7 10
10 11
11 7
10 9
Output
2
Note

Chọn các học sinh \(2\)\(7\).


Bình luận


  • 0
    duongnguyen0210 10:32 p.m. 26 Tháng 1, 2024

    người ra đề sửa lại inp của test 1 đi chứ sao không có "m "làm sao ac đc nhỉ, đc có 9/10 test

    1 phản hồi

    • 0
      chienthancontent 10:18 a.m. 4 Tháng 12, 2023

      sao test 1 chỉ có n mà ko có m thế ad