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.
Dữ liệu vào:
- Dòng
đầu là N, M (N <= 5000, M là số lượng liên lạc 1 chiều)
- Một số
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
Dữ liệu ra: Gồm 1 dòng ghi số học sinh
cần thầy nhắn tin.
Ví dụ:
MESSAGE.INP
|
MESSAGE.OUT
|
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
|
2
|
