COMPANY3 - Công ty
Giới hạn- Thời gian: 0.289s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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à beo_chay_so đã 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 beo_chay_so và beo_chay_so 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ệ. ( 1 ≤ N ≤ 1000, 1 ≤ M ≤ N(N–1)/2 )
Dòng thứ i trong M dòng tiếp theo ghi 2 số nguyên dương ai và bi với ý nghĩa người ai là sếp của bi.
Biết rằng giám đốc beo_chay_so 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.
Example
Input: 3 3 1 2 2 3 1 3 Output: 1
- Người up: cun
- Nguồn bài: IOICAMP 3