2018 Asia Singapore Preliminary Contest


2018-09-15 02:00 UTC

2018 Asia Singapore Preliminary Contest


2018-09-15 07:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -426 days 13:38:02

Time elapsed


Time remaining


Problem D
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