30850번 - Отличная лекция 다국어

문제

В одном очень известном университете часто важные люди приходят читать интересные лекции. Лекция обычно состоит из последовательности дедуктивных следствий «из A следует Б». При этом почти все люди обладают способностью к логическому мышлению: если они знают, что из A следует Б, и из Б следует В, то они вполне вправе считать, что из А следует В. Поскольку лектор не любит совсем бессмысленные следствия, то он никогда не выводит одно и то же утверждение дважды (т.е. не существует двух следствий вида «из А следует Б» и «из В следует Б»).

На очередную лекцию пришло несколько студентов. Каждый из них уже обладает некоторыми знаниями о мире (а именно, он знает, что некоторые утверждения — ложны, а некоторые — истинны). В ходе лекции лектор сообщает им некоторые дедуктивные следствия, которые, однако, в какой-то момент могут прийти в противоречие со знаниями студента (к примеру, если студент знал, что A ложно, а Б — истинно, а лектор сообщает, что «из Б следует А»). Вам необходимо для каждого студента узнать первый момент, когда рассуждения лектора приводят к противоречию с его знаниями. Противоречием называется момент, когда из набора истинных для студента утверждений с помощью дедутивных следствий лектора студент может логически вывести утверждение, которое он считает ложным.

Разберем пример типичной лекции. Предположим, что на лекции лектор сообщает следствия «из А следует Б», «из В следует Г», «из Б следует В», а студент считает, что А — истинно, а Г — ложно. Студент слушает следствия по одному, после добавления первого следствия «из А следует Б» студент думает, что Б — истинно. После добавления второго следствия противоречия также не происходит. После добавления третьего следствия «из Б следует В» студент думает, что В — истинно, и он (используя второе следствие лектора) может вывести, что Г — истинно, что противоречит его знаниям (ведь изначально он считал, что Г — ложно).

Если же в разобранном примере другой студент считал, что А — ложно, а Г — истинно, то для него противоречия не происходит ни в какой момент (даже зная все следствия лектора, он не может вывести из истинного утверждения вывести ложное).

입력

В первой строке входных данных содержится число M — количество дедуктивных следствий лектора (1 ⩽ M ⩽ 500 000). В следующих M строках содержатся описания следствий, каждое из них описывается двумя числами a_i и b_i , обозначающих антецедент (посылку) и консеквент (заключение) очередного следствия (a_i ≠ b_i, 1 ⩽ a_i, b_i ⩽ 500 000), т.е. лектор сообщает, что из утверждения a_i следует утверждение b_i, все b_i являются различными.

В следующей строке содержится число Q — количество студентов (1 ⩽ Q ⩽ 500 000). Далее содержится описание знаний каждого студента. Описание начинается с числа t_i — количества утверждений, которые студент считает истинным, после которого следует t_i чисел —- номеров этих утверждений. Далее описание содержит число f_i — количество утверждений, которые студент считает ложным, после которого следует f_i чисел — номеров этих утверждений.

Все номера утверждений лежат в пределах от 1 до 500 000. В отличие от действительности, каждый студент хоть что-то знает, т.е. t_i + f_i > 0. Отметим, что все номера утверждений, упомянутые одним студентом, различны. Общее количество упомянутых кем-либо утверждений (сумма t_i + f_i по всем i) не превосходит 500 000.

출력

Для каждого студента выведите номер первого следствия лектора, которое приводит к противоречию с его картиной мира, или −1, если они полностью согласны со всеми следствиями лектора.

제한

힌트