407568: GYM102830 D Useful Proofs

Often, when Aditya writes problems, he gets caught up in making sure that his solution is valid using a series of proofs. He has $$$n$$$ different propositions to consider, with labels from $$$1$$$ to $$$n$$$. He has $$$m$$$ implications proved already, where an implication is defined as a pair $$$(u , v)$$$, which means that if proposition $$$u$$$ is true, then proposition $$$v$$$ is also true. Note that you can combine implications to create new implications; for example if you have $$$(u, v)$$$ and $$$(v, w)$$$, then you can also create the implication $$$(u, w)$$$. Aditya's goal is to construct all possible implications between the $$$n$$$ propositions, but he recognizes that this might take significant time. Instead, he will pick a starting proposition, $$$s$$$, and you must find the number of new implications involving $$$s$$$ (of the form $$$(s, u)$$$ or $$$(u, s)$$$ for arbitrary implication $$$u \neq s$$$) that are not already proved by the $$$m$$$ implications Aditya already has.

The first line will consist of 3 space-separated integers $$$n, m, s$$$ ($$$1 \leq s \leq n \leq 10^5$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$) giving the number of propositions, number of already proved implications, and starting proposition. The next $$$m$$$ lines will consist of two space-separated integers $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), which indicates that Aditya has already proved the implication $$$(u_i, v_i)$$$.

Output the number of implications involving $$$s$$$ that Aditya has not already proven given the $$$m$$$ implications he has.

3 3 1
1 2
2 3
3 1

0

3 2 1
1 2
2 1

2

In the first case, all possible implications can already be proved. In the second case, the unproved implications involving $$$1$$$ are $$$(1, 3)$$$ and $$$(3, 1)$$$.