시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 64 MB | 12 | 3 | 3 | 27.273% |
Ever since George was little he had a dream: to sail around the world in a raft. He has bought a raft and enough supplies and took courses in swimming and self-defence (against sharks) – it seems that this summer, his dream will come true.
Just before he was going to leave, he realised that he doesn’t have any sense of orientation. It is endurable in a city, but on an open sea? He wouldn’t be able to stop and ask for directions, that’s for sure. . .
As a result, he is now helplessly standing in the middle of the local inn – and a quite stinky one – and trying to hire an experienced sailor as a navigator. Unfortunately, sailors are quite sociable fellows – each one has a few friends he won’t sail without.
George chatted with all the sailors and determined, who wouldn’t sail without whom. As it turned out, the relationship is not necessarily mutual – for example, Cripple Jack owes Lazy-eyed Tom a case of undisclosed alcoholic beverage. Thus, Lazy-eyed Tom demands to have Cripple Jack with him, while Cripple Jack would happily sail without Lazy-eyed Tom.
The raft can only carry so many sailors and George needs at least one as a navigator. Your task is to determine the minimal number of sailors which George has to hire while still fulfilling their demands.
The first line consists of integers N and M separated by a space. N (1 ≤ N ≤ 100 000) represents the number of available sailors and M (1 ≤ M ≤ 1 000 000) the number of demands. The sailors are numbered 1 through N.
The second part of the input consists of M rows having the form a b (1 ≤ a, b ≤ N, a ≠ b). Each row represents one demand: sailor a won’t accept the job unless you also hire sailor b.
Output one line consisting of a single positive integer – the smallest possible number of sailors George must hire.
5 6 1 2 2 4 4 3 3 2 5 1 5 4
3