458. Восстановление отчётов

Не решаласьСредняя

Программист Филипп увидел резкое увеличение ошибок в своей программе. Чтобы понять причины, он принялся изучать отчёты пользователей. Однако вскоре Филипп заметил, что отчёты фиксируют не все переходы между страницами программы. Это вызвало у него вопрос: сколько ещё страниц программы недоступны для анализа по имеющимся отчётам?

Формат ввода

Первая строка содержит два целых числа: nn (1n103)(1 \le n \le 10^3) — количество страниц в программе, mm (0m106)(0 \le m \le 10^6) — количество записей в отчётах.

Вторая строка содержит nn строк, описывающих названия страниц.

В третьей строке содержится одна строка — название главной страницы.

В следующих mm строках перечислены записи в отчётах. Запись состоит из двух строк: первая — страница, с которой ушёл пользователь, и вторая — страница, на которую пользователь перешёл.

Гарантируется, что суммарная длина строк во входных данных не превосходит 10610^6.

Формат вывода

Необходимо вывести количество страниц приложения, до которых невозможно восстановить путь по отчётам.

Ограничения

Ограничение времени

1 с

Ограничение памяти

64 МБ

Пример 1

Ввод
4 3
a b c d
a
a b
b c
a c
Вывод
1

Пример 2

Ввод
5 5
main reader webpage profile alice
main
main reader
reader main
webpage profile
profile alice
alice main
Вывод
3

Теги

Нужно войти, чтобы отправить решение.Войти