Mail of the Sponsor#37
You may remember the problem "The word of sponsor" from a previous contest, where the sponsor wanted to send prizes to the winners after the event.
However, the postal system is not perfect, and not all prizes can be delivered to the participants. In the country, there are post offices, numbered from to . The sponsor sends prizes from post office number . The postal transportation system is defined by given pairs of post offices between which mail can be sent.
Before the new contest, the sponsor wants to ensure that prizes can be delivered to all participants, regardless of where they live or which post office they use. To achieve this, the sponsor is willing to establish new connections between some pairs of post offices at their own expense.
Your task is to determine the minimum number of new connections that must be established so that prizes can be delivered from post office to every other post office in the country, regardless of where the recipient lives or which post office they use.
The first line contains three integers: the number of post offices (1 \le n \le 10^5), the number of the post office used by the sponsor (1 \le s \le n), and the number of existing connections (0 \le k \le 10^5).
Each of the next lines contains two integers and — the numbers of post offices between which mail delivery is possible ( and are distinct numbers in the range ). All pairs are unique.
Print a single integer — the minimum number of new connections that must be added so that mail can be delivered from post office to every other post office.
Example 1