Problem Statement

You are given a directed graph with $N$ vertices numbered from $0$ to $N-1$ and $M$ edges numbered from $0$ to $M-1$.
Ouji-kun is initially at vertex $0$.
Each time $1$ second passes, Ouji-kun moves by $1$ vertex along one of the directed edges going out of the vertex he is currently at. However, he does not move at $0$ seconds.
Find the number of vertices where Ouji-kun may be after $T+0.5$ seconds.
However, if no directed edge goes out of his vertex at the time of a move, Ouji-kun cannot move and disappears.
Also, moves are sufficiently fast, and the time they take can be ignored.

Note that this graph may contain self-loops and multiple edges, and it is not necessarily connected.

Input

$N\ M\ T$
$a_1\ b_1 $
$a_2\ b_2 $ 
$:$
$a_M\ b_M$

• $1 \leq N \leq 100$
• $0 \leq M \leq 10000$
• $0 \leq T \leq 10^{18}$
• In the $M$ lines starting from line $2$, the vertex numbers $a_i$ and $b_i$ ($0\ \leq a_i,\ b_i\ < N$) connected by the $i$-th directed edge of the graph are given. This means that the $i$-th edge is a directed edge along which one can move from $a_i$ to $b_i$.
• All inputs are given as integers.

Output

Output the number of vertices where Ouji-kun may be after $T+0.5$ seconds. Print a newline at the end.

Sample

5 6 10
0 1
1 2
2 3
3 0
1 4
4 0

5

5 4 5
0 1
1 2
2 3
3 4

0

1 1 10
0 0

1