Công ty

View as PDF

Submit solution


Points: 0.63 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
IOICAMP 3
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong tập đoàn Big Soft của ~MSN~, có một công ty nhỏ có nhiều người tài nhưng do giám đốc công ty đó là beochayso đã xây dựng một hệ thống nhân sự rất phức tạp nên công ty không thể phát triển tốt được. Hệ thống nhân sự được bố trí như sau. Đứng cao nhất chính là giám đốc beochayso và beochayso là sếp của mọi người khác. Sau vị giám đốc này là một mối quan hệ nhằng nhịt giữa sếp và nhân viên. Tuy nhiên những mối quan hệ này vẫn phải đảm bảo 2 nguyên tắc sau:

Nếu ~A~ là sếp của ~B~ và ~B~ là sếp của ~C~ thì ~A~ cũng là sếp của ~C~.

Không tồn tại đồng thời ~A, B, C~ sao cho ~A~ là sếp của ~B, B~ là sếp của ~C~ và ~C~ là sếp của ~A~.

~MSN~ đang muốn tái thiết lại công ty, bạn hãy giúp ~MSN~ giữ lại nhiều người nhất có thể để sao cho không có ai là sếp của ai trong số những người được chọn, có như vậy mọi người mới phát huy hết khả năng của mình được.

Input

Dòng đầu tiên ghi 2 số nguyên dương ~N~ và ~M~ là số người của công ty và số mối quan hệ. ~\left(1 \leq N \leq 1000, 1 \leq M \leq \frac{N(N-1)}{2}\right)~

Dòng thứ ~i~ trong ~M~ dòng tiếp theo ghi 2 số nguyên dương ~a_i~ và ~b_i~ với ý nghĩa người ~a_i~ là sếp của ~b_i~.

Biết rằng giám đốc beochayso luôn được ký hiệu là người thứ ~1~.

Output

Gồm một dòng duy nhất ghi số nguyên dương ~S~ là số người tối đa có thể giữ lại.

Sample Input

3 3
1 2
2 3
1 3

Sample Output

1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.