Cave Exploration

Alice is a soccer coach who occasionally bring her soccer team to explore Caveland (that can be modeled as an undirected unweighted connected graph) for special event, e.g. for initiation ceremony, to celebrate birthdays, etc. Caveland has $N$ junctions and $M$ tunnels.

Caveland is quite prone to flooding, but that does not stop
Alice and her soccer team from doing what they enjoy. You are
Bob, Alice’s good friend. You want to ensure Alice and her
soccer team are as safe as possible by letting her know which
junction(s) is/are safe(r) than the rest. You decide that a
junction $v$ is considered
to be safe(r) if **any one tunnel** is
flooded, Alice and her soccer team can still go out from
junction $v$ to the
entrance of Caveland (which is always junction $0$) via a non-flooded path.

For this example, junctions $\{ 0, 1, 2, 3\} $ are considered safe(r). If tunnel $0–2$ is flooded for example, Alice and her soccer team can detour via path $2 \rightarrow 3 \rightarrow 1 \rightarrow 0$ to reach Caveland entrance. However junctions $\{ 4, 5, 6, 7, 8\} $ are quite dangerous. If tunnel $2–8$ (or tunnel $3–4$) is flooded, Alice and her soccer team will be trapped (cannot reach safety/junction $0$).

The first line of input consists of $2$ integers: $N$ and $M$. ($2 \leq N \leq 10\, 000$, $1 \leq M \leq min(N(N-1)/2, 100\, 000)$). The next $M$ lines contains $M$ pairs of integers $u$ and $v$ that describe $0$-based indices of the two junctions that are connected with a tunnel in Caveland ($0 \leq u, v < N$, and $u \neq v$). No two junctions are directly connected with more than one tunnel. You are guaranteed that junction $0$ can reach all the other $N-1$ junctions (if there is no flood).

Print an integer in one line: The total number of junction(s) in Caveland that is/are safe(r) for Alice and her soccer team to explore. The actual junction numbers are not needed.

Sample Input 1 | Sample Output 1 |
---|---|

9 10 0 1 0 2 1 3 2 3 2 8 3 4 4 5 4 6 5 7 6 7 |
4 |