#174 I Want to Cycle.

Loading problem...

Preparing the statement, recent submissions, and submit form.

#174 I Want to Cycle. | DOJ

Time limit: 2000 ms
Python time limit: 5000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

You are given a directed simple graph with $N$ vertices and $M$ edges.

We say that a vertex $v$ can visit a cycle if, starting from $v$ and moving along directed edges, it is possible to reach a vertex that belongs to some directed cycle.

Find the number of vertices from which no cycle can be visited.

Input

The input is given in the following format.

$N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$

The edge $u_i\ v_i$ represents a directed edge from vertex $u_i$ to vertex $v_i$ .

Output

Print the number of vertices from which no cycle can be visited.

Constraints

$1 \le N \le 100\,000$ .
$0 \le M \le 100\,000$ .
$1 \le u_i,v_i \le N$ ( $1 \le i \le M$ ).
$u_i \ne v_i$ ( $1 \le i \le M$ ).
No directed edge appears more than once.

Subtasks

#	Score	Constraints
1	100	The full constraints apply.

Samples

Sample 1

Input

Output

There is no cycle in the graph, so no vertex can visit a cycle.

Sample 2

Input

Output

Vertices $2$ and $3$ are contained in a cycle. From vertices $1$ and $4$ , this cycle can be visited.

From vertices $5$ and $6$ , no cycle can be visited, so the answer is $2$ .

Sample 3

Input

Output

Every vertex can visit some cycle.

Editorial

View editorial