Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

COMPANY3 - Công ty

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

Được gửi lên bởi:special_one
Ngày:2008-12-10
Thời gian chạy:0.289s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:IOICAMP 3

hide comments
2019-05-24 01:57:17
Code AC :)) :
https://ideone.com/hCeOAb
2016-11-23 06:04:13 Lê Hoàng Vũ
Bài toán đưa về: Xóa ít đỉnh nhất sao cho sau khi xóa, đồ thị là một tập độc lập (Nói cách khác, đồ thị không còn cạnh nào)
==>> Minimum Vertex Cover

Last edit: 2016-11-23 06:04:38
2016-11-22 08:35:17


Last edit: 2016-11-23 03:40:04
2016-11-03 15:22:47
Code pascal:
http://shink.in/5V279
2014-09-07 16:03:54 a;slkfjasl;fkj
toàn cho test kiểu khó nghĩ -_-
2010-11-15 13:40:07 mr_
A là sếp B, B là sếp C ==> A là sếp C.
Vậy cho hỏi nếu xóa B thì A còn là sếp C không ?
2010-06-07 02:50:35
"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."

=> Hoặc là loại bỏ beo_chay_so đầu tiên, hoặc là beo_chay_so làm việc một mình =))

Last edit: 2010-06-07 02:52:34
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.