Post Office

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type

Tabby, Teddy's sister, wants to perform some direct-mail promotions! She lives in the country of Byteland, which consists of N cities numbered from 1 to N inclusive. These cities are connected by M bidirectional roads. Tabby can access a post office in city A, and the post office can deliver to any city as long as there is a path from the post office to that city via some of the roads. To estimate the effectiveness of the promotion, Tabby wants to figure out how many cities the post office can deliver to (including its own city). Can you help her?

Constraints

2\le N\le 10^5

1\le M\le \min(\binom N2, 10^5)

1\le A\le N

Input Specification

The first line will contain three integers N, M, and A: the number of cities, the number of bidirectional roads, and the city that Tabby's post office is located in.

The next M lines will each contain two integers U_i and V_i, indicating that there is a bidirectional road between city U_i and city V_i

Output Specification

One integer, the number of cities that the post office can deliver to

Sample Input

7 6 2
1 6
3 6
2 7
4 7
2 4
7 5

Sample Output

4

Sample Explanation

The graph looks as such:

When looking at city 2, we see that it is connected to 4 cities in total: cities 2, 4, 7, and 5. Thus, the post office can deliver to 4 cities.


Comments

There are no comments at the moment.