Problem D
Through the Grapevine

Pieter Brueghel the Younger, Web Gallery of Art

According to Wikipedia, to hear something “through the grapevine” is to learn of something informally and unofficially by means of gossip or rumor. In this problem, you are tasked with determining how many people will hear about a particular rumor “through the grapevine” after a certain number of days.

Rumors are always started by a single person. On any given day, a person who knows the rumor can spread it by telling the people that they know. Upon hearing of the rumor, that person must wait until the following day before they can begin to spread it themselves. Furthermore, some people are skeptical and will only spread the rumor once they’ve heard it from a number of distinct sources. However once a person has heard the rumor from enough people, they will always try to spread the rumor to as many people as possible.

Input

The first line will contain three integers: $0 < n \leq 100\, 000$, $0 < m \leq 100\, 000$, and $0 \leq d \leq 10\, 000$, where $n$ is the number of people, $m$ is the number of connections, and $d$ is the number of days that elapse.

The next $n$ lines will each consist of a unique string $s$ and an integer $0 \leq t \leq 1000$ where $s$ is the name of a person and $t$ is their level of skepticism. In other words, person $s$ must hear the rumor from $t$ distinct other people before $s$ will begin spreading the rumor.

This is followed by $m$ lines each consisting of two strings $u$ and $v$ which indicates that person $u$ and person $v$ know each other. Each of these lines represents a unique pair of persons.

The final line will contain a single string $r$, the name of the person that the rumor originates from. Note that $r$ is the only person with skepticism $t = 0$. All strings are between $1$ and $20$ characters long and consists only of English lowercase or uppercase letters and digits.

Output

Output a single integer: the number of people (not including person $r$) that have heard the rumor after $d$ days.

3 2 1
Alice 0
Bob 1
Carol 1
Alice Bob
Bob Carol
Alice

1

5 5 3
Alice 0
Bob 1
Carol 1
Dan 3
Erin 1
Alice Bob
Alice Carol
Bob Dan
Carol Dan
Dan Erin
Alice

3