D. Useful Proofs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

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

Examples
Input
3 3 1
1 2
2 3
3 1
Output
0
Input
3 2 1
1 2
2 1
Output
2
Note

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)$$$.