Description
Money is a very sociable person. Wherever he goes on the NTHU campus, he always seems to run into someone he knows. His friends come from many different departments, and he even knows the names of his friends' friends
.
One day, while walking around campus, Money suddenly wondered:
“Wait... how large is my social network?”
So, he decided to find all of his friends, as well as all of his friends' friends.
There are \(N\) people in NTHU, numbered from \(1\) to \(N\), and there are \(M\) friendship relationships among them.
Each friendship relationship is represented by two integers \(a\) and \(b\), meaning that person \(a\) and person \(b\) are friends.
Friendship is bidirectional. In other words, if \(a\) is a friend of \(b\), then \(b\) is also a friend of \(a\).
Given Money's person number \(K\), your task is to determine how many distinct people are within at most two friendship relationships from Money.
- A degree-1 friend is someone who is directly friends with Money.
- A degree-2 friend is someone who is a friend of one of Money's friends.
A person should be counted only once, even if Money can reach that person through multiple different friendship paths.
Money himself should not be counted.
Constraints
\[ 1 \le N \le 10^5 \] \[ 0 \le M \le \min\left(\frac{N(N-1)}{2},\,2\times10^5\right) \] \[ 1 \le K \le N \]
For every friendship pair \((a,b)\):
- \(1 \le a,b \le N\)
- \(a \ne b\)
- The same friendship relationship will not appear more than once.
Explanation
Money is person \(1\).
His degree-1 friends are \(2\) and \(3\).
His degree-2 friends are \(4\) and \(5\).
Although person \(5\) can be reached through both person \(2\) and person \(3\), person \(5\) is counted only once.
Therefore, the size of Money's social network within two degrees is \(4\).
Input
The first line contains three integers: \[ N \quad M \quad K \] \(N\) is the total number of people. \(M\) is the number of friendship relationships. \(K\) is Money's person number. The next \(M\) lines each contain two integers: \[ a \quad b \] indicating that person \(a\) and person \(b\) are friends.
Output
Print one integer: the number of distinct people who are within at most two friendship relationships from Money.