Virus

Problem Statement

There was a virus outbreak in $s$, the city you are living in!

Some cities on the map are connected to each other by roads; and because there is no lockdown, if a virus is present in a city, then the virus would spread to all road-connected cities of that one city within just $1$ day!

There are total of $r$ roads on the map. It has been $d$ days since the outbreak has started at your city $s$. How many cities have been infected?

Input

Your first line will contain $r$ and $d$ as space-separated integers. $r$ represents the number of roads in the given map, and $d$ represents the number of days since the outbreak.

Your next line will contain $s$, the name of the city in which the virus outbreak has started.

Your next $r$ lines will contain $2$ space-separated city names, specifying that there is a road between the $2$ cities where the virus could travel within a single day.

Output

A single integer representing the total number of cities affected by the virus after $d$ days.

Constraints

For all test cases:

• $0 \le r \le 10^5$
• $0 \le d \le 10^3$
• All city names will comprise of only lower-case English letters.

Example 1

14 2
clayton
burwood boxhill
mulgrave clayton
burwood glenwaverley
mulgrave rowville
rowville wantirnasouth
clayton chadstone
chadstone malverneast
clayton glenwaverley
malverneast moorabbin
burwood chadstone
camberwell burwood
springvale clayton
glenwaverley wantirnasouth
ringwood bayswater

9

Example 2

3 0
melbourne
melbourne sydney
sydney canberra
canberra melbourne

1

Example 3

24 4
nyc
charleston pittsburgh
montpelier albany
concord montpelier
portland augusta
pittsburgh dc
albany hartford
washingtondc richmond
richmond roanoke
philadelphia trenton
trenton newark
newark nyc
raleigh norfolk
newark hartford
portland boston
providence hartford
boston providence
norfolk richmond
raleigh durham
durham roanoke
harrisburg dc
philadelphia harrisburg
harrisburg dover
philadelphia atlanticcity
boston concord

11

Example 4

7 1000
earth
sun mercury
mercury venus
mars jupiter
jupiter saturn
saturn uranus
uranus neptune
neptune pluto

1

Python Template

r, d = map(int, input().split())
s = input()
roads = [tuple(input().split(" ")) for _ in range(r)]

# print(...)