19986번 - Прогулка по зоопарку 스페셜 저지다국어

Андрей Сергеевич работает сторожем в зоопарке. Однажды утром он пришел на работу и обнаружил анонимную записку, в которой сообщалось, что ночью хулиганы поменяли таблички на двух клетках. Андрей Сергеевич должен срочно решить проблему и поменять таблички обратно. К сожалению, Андрей Сергеевич хорошо разбирается в охране зоопарка, но не столь силен в зоологии, так что понять по внешнему виду животного, что это за зверь, он не в силах.

К счастью, на каждой табличке помимо наименования животного написан также порядковый номер. Номера на всех табличках разные. Обойдя зоопарк, Андрей Сергеевич составил его карту. В зоопарке есть $n$ перекрестков, соединенных $m$ дорожками. Чтобы встречные потоки посетителей не мешали друг другу наслаждаться посещением зоопарка, по каждой дорожке разрешено перемещаться ровно в одном направлении, от начала дорожки к ее концу. При этом от одного перекрестка до другого идет максимум одна дорожка, не существует дорожки, которая начинается и заканчивается на одном и том же перекрестке. Рядом с каждой дорожкой расположена ровно одна клетка с животным. 

Перекрестки в зоопарке пронумерованы от 1 до $n$, Андрей Сергеевич для каждой дорожки записал номер перекрестка, на котором она начинается, номер перекрестка, на котором она заканчивается, и номер на табличке, в настоящий момент находящейся на клетке с животным около этой дорожки.

Около входа в зоопарк расположен список тематических маршрутов, рекомендуемых сотрудниками зоопарка. Каждый тематический маршрут задается начальным перекрестком, конечным перекрестком и последовательностью дорожек, по которым следует пройти, чтобы изучить соответствующих животных. Первая дорожка в маршруте начинается на его начальном перекрестке, каждая следующая дорожка начинается на перекрестке, где заканчивается предыдущая, а последняя дорожка завершается на конечном перекрестке маршрута. Каждая дорожка задается номером таблички на клетке с животным, расположенной около соответствующей дорожки. Никакой маршрут не проходит через один перекресток два раза. По каждой дорожке в зоопарке проходит хотя бы один тематический маршрут.

Андрею Сергеевичу тут же пришла в голову гениальная мысль: используя информацию о тематических маршрутах, он может выяснить, какие две таблички хулиганы поменяли местами. Но, к сожалению, задача оказалась для него слишком сложной. Помогите сторожу выяснить, какие две таблички поменяли местами, чтобы он успел восстановить порядок до открытия зоопарка.

Выясните, какие две таблички можно поменять местами, чтобы все тематические маршруты в зоопарке действительно существовали. Гарантируется, что это можно сделать.

В первой строке содержится два целых числа $n$ и $m$ --- количество перекрестков и количество дорожек, соответственно ($1 \le n, m \le 100\,000$). Все перекрестки пронумерованы от 1 до $n$.

Следующие $m$ строк содержат по три целых числа $a_i$, $b_i$ и $c_i$ --- номер перекрестка, где начинается очередная дорожка, номер перекрестка, где она заканчивается, и номер на табличке на расположенной на этой дорожке клетке ($1 \le a_i, b_i \le n, a_i \ne b_i, 1 \le c_i \le m$). Все номера на табличках различны.  

В следующей строке содержится целое число $k$ --- количество тематических маршрутов по зоопарку ($1 \le k \le 100\,000$).

Следующие $2k$ строк описывают маршруты.  Первая строка описания маршрута содержит три целых числа $l_i$, $s_i$ и $t_i$ --- число дорожек в маршруте, номер перекрестка, где маршрут начинается и номер перекрестка, где он заканчивается ($1 \le l_i \le n$, $1 \le s_i, t_i \le n$, $s_i \ne t_i$). Во второй строке содержится $l_i$ чисел --- последовательность номеров на табличках на клетках, вдоль которых проходит этот маршрут.

Суммарная длина всех маршрутов не превышает $100\,000$. Никакой маршрут не проходит через один перекресток два раза. По каждой дорожке в зоопарке проходит хотя бы один тематический маршрут.

Выведите два различных числа --- номера табличек на клетках, которые Андрей Сергеевич должен поменять местами, чтобы все тематические маршруты снова существовали. Если существует несколько решений, то выведите любое из них.

Карта зоопарка из примера и тематические маршруты приведены на следующем рисунке.

Видно, что если поменять местами таблички на клетках с номерами 3 и 5, то карта приобретет следующий вид и оба маршрута действительно будут существовать на карте.