Domino Effect

Points: 10

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

There are $N$ ~N~ dominoes arranged in a peculiar order labeled from $1$ ~1~ to $N$ ~N~.

Some dominoes knock down other dominoes when they are knocked down.

It is possible to knock down an entire chain of dominoes by knocking down a single one.

You are given a list of $M$ ~M~ pairs in the form a b, where domino a will knock down domino b when knocked down.

Determine the minimum number of dominoes you need to knock down manually in order to knock down all of them.

$1 \le N, M \le 10^5$ ~1 \le N, M \le 10^5~

$1 \le a, b \le N$ ~1 \le a, b \le N~

$a \ne b$ ~a \ne b~

The first line of input contains $2$ ~2~ space-separated integers $N$ ~N~ and $M$ ~M~.

The next $M$ ~M~ lines of input each contain $2$ ~2~ space-separated integers $a$ ~a~ and $b$ ~b~.

Output a single integer, the minimum number of dominoes you need to knock down manually.

It is optimal to knock down domino $2$ ~2~, which will result in the following chain: $2 \rightarrow 3 \rightarrow 4 \rightarrow 1$ .

Knocking down domino $2$ ~2~ will knock down dominoes $1$ ~1~, $3$ ~3~, and $4$ ~4~.

Domino $5$ ~5~ needs to be knocked down separately.

Comments