Mail of the sponsor
Mail of the sponsor
You remember the problem "The word of sponsor" from New Year contest. I remind you briefly that problem: after the event finished, the sponsor wanted to send out the prizes for winners.
But the postal system is not perfect and not all the prizes can be delivered to participants. There are n post offices in the country, numbered from 1 to n. The sponsor sends the prizes from the office number s. Also, we know the mail transportation system - the pairs of post offices between which the mail can be passed.
Before the new competition the sponsor decided to guarantee the safe delivery of prizes. To do this, the sponsor is ready to establish new links between some pairs of post offices. Your task is to find the least amount of new connections, so that prizes can be delivered after the competition to all participants, regardless of where they live and which post office use.
Input data
First line contains three integers - the number of post offices n (1 ≤ n ≤ 10^5), the number of post office the sponsor uses s (1 ≤ s ≤ n) and the number of links between the pairs of offices k (0 ≤ k ≤ 10^5).
Each of the next k lines contains 2 numbers: a and b - the numbers of post offices, between which the mail transportation exists (a and b are different numbers from interval [1; n]). All the pairs (a, b) are different.
Output data
Print one number - the minimum possible number of new connections to be created, so that the mail can be delivered from s to any other post office.
Examples
5 1 4 1 2 2 3 1 3 4 5
1