C. Управление зависимостями
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп разрабатывает проект на языке Vaja и использует популярную систему управления зависимостями Vamen. С точки зрения Vamen и проекты, и библиотеки на Vaja называются просто проектами.

В Vamen каждый проект имеет уникальное название из строчных латинских букв длины от 1 до 10 и версию — положительное целое число от 1 до 106. Каждый проект (помните, что в этот термин включается не только название, но и конкретная версия) может зависеть от других проектов. Конечно, все зависимости ациклические.

Вам задан набор описаний проектов. Первый из заданных проектов — это тот, который в настоящий момент разрабатывается Поликарпом. Помогите Поликарпу определить все проекты, от которых прямо или по цепочке зависит проект Поликарпа.

Возможно, что проект Поликарпа зависит от одного и того же проекта разных версий (то есть имя проекта одинаково, а версии разные). В этом случае происходит разрешение коллизий, которое для разрабатываемого проекта выбирает такую версию зависимости, длина цепочки зависимостей до которой минимальна. Если таких версий несколько, выбирается максимальная версия из них.

Таким образом, если проект Поликарпа зависит (прямо или по цепочке) от нескольких проектов с одинаковыми названиями, но разными версиями, то необходимо выбрать такую версию, длина цепочки зависимостей до которой от проекта Поликарпа минимальна (если таких версий несколько — максимальную из них). Именно эта версия для заданного названия проекта используется как действительная зависимость, остальные версии и их зависимости игнорируются.

Формально, необходимо выбрать такой набор проектов минимального размера, чтобы выполнялись следующие условия:

  • выбран проект Поликарпа;
  • проект Поликарпа прямо или косвенно зависит от каждого из выбранных проектов;
  • нет двух выбранных проектов с одинаковыми названиями;
  • для каждого проекта x, от которого напрямую зависит некоторый выбранный проект или проект Поликарпа, верно, что либо этот проект x тоже выбран, либо выбран проект y с таким же названием, но другой версией, причем либо цепочка зависимостей от проекта Поликарпа до проекта y короче, чем до проекта x, либо цепочки имеют равную длину, и версия проекта y больше, чем версия проекта x.

Выведите все зависимости (прямые или по цепочке) проекта Поликарпа. Сам проект Поликарпа выводить не нужно. Выводите зависимости в порядке лексикографического порядка увеличения названий.

Входные данные

В первой строке следует целое число n (1 ≤ n ≤ 1 000) — количество проектов языка Vaja.

Далее следует описание всех n проектов. Каждый проект задается строкой, состоящей из имени (непустая строка, состоящая из строчных букв латинского алфавита; длина не превосходит 10) и версии (целое число от 1 до 106), которые записаны через одиночный пробел. Затем следует строка с количеством непосредственных зависимостей (целое число от 0 до n - 1), затем сами зависимости по одной в строке в произвольном порядке. Каждая зависимость задается как название и версия (записаны через одиночный пробел). Проекты заданы в произвольном порядке, но первый из них — проект Поликарпа. Описание проектов разделяется пустой строкой.

Гарантируется, что циклических зависимостей нет. Проекты разделены одиночными пустыми строками. Считайте, что проект может зависеть от проекта, имеющего такое же название, но отличную версию.

Ознакомьтесь с примерами для лучшего понимания условия.

Выходные данные

Выведите все зависимости (прямые или по цепочке) проекта Поликарпа. Выводите зависимости в порядке лексикографического порядка увеличения названий.

Примеры
Входные данные
4
a 3
2
b 1
c 1
 
b 2
0
 
b 1
1
b 2
 
c 1
1
b 2
Выходные данные
2
b 1
c 1
Входные данные
9
codehorses 5
3
webfrmk 6
mashadb 1
mashadb 2
 
commons 2
0
 
mashadb 3
0
 
webfrmk 6
2
mashadb 3
commons 2
 
extra 4
1
extra 3
 
extra 3
0
 
extra 1
0
 
mashadb 1
1
extra 3
 
mashadb 2
1
extra 1
Выходные данные
4
commons 2
extra 1
mashadb 2
webfrmk 6
Входные данные
3
abc 1
2
abc 3
cba 2

abc 3
0

cba 2
0
Выходные данные
1
cba 2
Примечание

Первый пример изображён на рисунке ниже. Стрелка из проекта A в проект B означает, что проект B напрямую зависит от проекта A. Закрашены проекты, от которых зависит проект Поликарпа «a» с версией 3.

Второй пример изображён на рисунке ниже. Стрелка из проекта A в проект B означает, что проект B напрямую зависит от проекта A. Закрашены проекты, от которых зависит проект Поликарпа «codehorces» с версией 5. Обратите внимание, взят проект «extra 1», а не «extra 3», так как проект «mashadb 1» и все его зависимости отброшены из-за проекта «mashadb 2».