Задача №114035. Отличная лекция
В одном очень известном университете часто важные люди приходят читать интересные лекции. Лекция обычно состоит из последовательности дедуктивных следствий «из 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 , если они полностью согласны со всеми следствиями лектора.
Тесты к этой задаче состоят из четырех групп.
- Тесты 1-2. Тесты из условия, эта группа оценивается в ноль баллов.
- Тесты 3–12. В тестах этой группы M , Q ≤ 200 . Эта группа оценивается в 20 баллов.
- Тесты 13–20. В тестах этой группы M , Q ≤ 2000 . Эта группа оценивается в 20 баллов.
- В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 60 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы. Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп.
6 1 2 2 5 5 7 5 6 2 3 2 4 3 2 1 5 2 3 7 1 2 1 6 1 6 1 2
3 4 -1
5 1 2 2 3 3 4 4 5 5 1 6 1 2 1 4 1 4 1 2 1 2 1 3 1 3 1 2 1 1 1 5 1 5 1 1
3 5 2 5 4 5