- Описание
- Отправленные решения
458. Восстановление отчётов
Программист Филипп увидел резкое увеличение ошибок в своей программе. Чтобы понять причины, он принялся изучать отчёты пользователей. Однако вскоре Филипп заметил, что отчёты фиксируют не все переходы между страницами программы. Это вызвало у него вопрос: сколько ещё страниц программы недоступны для анализа по имеющимся отчётам?
Формат ввода
Первая строка содержит два целых числа: $n$ $(1 \le n \le 10^3)$ — количество страниц в программе, $m$ $(0 \le m \le 10^6)$ — количество записей в отчётах.
Вторая строка содержит $n$ строк, описывающих названия страниц.
В третьей строке содержится одна строка — название главной страницы.
В следующих $m$ строках перечислены записи в отчётах. Запись состоит из двух строк: первая — страница, с которой ушёл пользователь, и вторая — страница, на которую пользователь перешёл.
Гарантируется, что суммарная длина строк во входных данных не превосходит $10^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