In case of fire, exit building before tweeting about it.
Nobody is surprised nowadays hearing a story about someone writing to a blog or a social network
about an accident before calling the rescue service. Knowing this attachment to internet technologies,
the Japanese authorities suggest people to use Twitter to alert their friends and relatives about an earthquake.
Indeed, since the propagation velocity of seismic waves is no more than five kilometers per second,
people who are far enough from the epicenter will be able to read about the earthquake several seconds before
the wave hits them. These seconds may become crucial for some of them…
Each Twitter user has a list of followers. A tweet (message) of a user is seen by all of his followers.
Each of them can retweet this tweet. As a result, it will become available to all their followers.
These followers can in turn retweet the retweet, and so on…
Retweet gets the string «RT @nick: » appended to its beginning, where
nick is the name of the user whose tweet (or retweet) is retweeted.
Since the length of a tweet must not exceed 140 symbols, any retweet violating this restriction
will not be sent.
The Japanese Fire and Disaster Management Agency wants to test the idea of Twitter alerts
by conducting an experiment. They have chosen a group of people and want to calculate how
many of them will learn about an earthquake, if only person will be notified of it.
Input
The first line contains the number n of Twitter users chosen for the experiment (2 ≤ n ≤ 100).
The users are described in the next n lines in the following format: username, the number of followers,
and the list of their names. The lists of followers can only contain names of other users chosen for the experiment.
The names are distinct nonempty strings of length at most 30, consisting of uppercase and lowercase English letters.
The last line contains a tweet about an earthquake sent by the user whose name is the first in the input.
The tweet is a nonempty string consisting of symbols with ASCII codes in the range
from 32 to 127; the length of the string is at most 140 symbols.
Output
In the first line output the number of users who will learn about the earthquake.
Then output their names in any order, one name per line.
Sample
input | output |
---|
5
Miyako 1 Sae
Yuno 2 Miyako Sae
Nazuna 1 Nori
Sae 1 Yuno
Nori 1 Nazuna
Hidamari is going to collapse!!!
| 3
Miyako
Sae
Yuno
|
Problem Author: Dmitry Ivankov
Problem Source: Open Ural FU Championship 2011