D. Открытый протокол
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Двум участникам предоставили по паре чисел от 1 до 9, так что ровно одно число встречается в обеих парах. Они хотят определить, какое число в их парах совпадает, используя канал связи, к которому у вас есть доступ, так, чтобы вы не могли определить это число.

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

Определите, можете ли вы однозначно определить число, которое совпадает у двух участников, или верно ли, что оба участника могут определить это число, а вы — нет.

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

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

Во второй строке $$$n$$$ пар целых чисел, каждое от $$$1$$$ до $$$9$$$, — пары чисел, который первый участник передал второму.

В третьей строке $$$m$$$ пар целых чисел, каждое от $$$1$$$ до $$$9$$$, — пары чисел, которые второй участник передал первому.

Все пары внутри каждого из двух множеств будут уникальными (в частности, если в множестве есть пара $$$(1,2)$$$, в нем не будет пары $$$(2,1)$$$). Каждая пара содержит два различных числа.

Гарантируется, что переданные множества пар не противоречат условию, иными словами, существуют пара в первом множестве и пара во втором множестве, у которых совпадает ровно одно число.

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

Если вы можете однозначно определить число, которое совпадает, выведите это число.

Иначе, если вы можете однозначно утверждать, что оба участника знают это число, а вы — нет, выведите $$$0$$$.

Иначе выведите $$$-1$$$.

Примеры
Входные данные
2 2
1 2 3 4
1 5 3 4
Выходные данные
1
Входные данные
2 2
1 2 3 4
1 5 6 4
Выходные данные
0
Входные данные
2 3
1 2 4 5
1 2 1 3 2 3
Выходные данные
-1
Примечание

В первом примере первый участник передал пары $$$(1,2)$$$ и $$$(3,4)$$$, а второй – $$$(1,5)$$$, $$$(3,4)$$$. Поскольку вы знаете, что реальные пары имеют ровно одно общее число, не может быть, чтобы оба участника видели $$$(3,4)$$$. Значит, числа у первого участника — $$$(1,2)$$$, а у второго — $$$(1,5)$$$, и вы однозначно знаете, что общее число — $$$1$$$.

Во втором примере либо у первого участника пара $$$(1,2)$$$, а у второго пара $$$(1,5)$$$, либо у первого пара $$$(3,4)$$$, а у второго пара $$$(6,4)$$$. В первом случае они оба знают что общее число — $$$1$$$, а во втором они оба знают, что общее число — $$$4$$$. У вас нет достаточной информации, чтобы отличить $$$1$$$ от $$$4$$$.

В третьем примере у первого участника пара $$$(1,2)$$$, и он не может определить число, так как с его точки зрения у второго участника может быть либо $$$(1,3)$$$, и тогда общее число — $$$1$$$, либо $$$(2,3)$$$, и тогда общее число — $$$2$$$. Несмотря на то, что второй участник однозначно знает общее число, ни вы, ни первый участник не знаете его, следовательно правильный вывод для теста — $$$-1$$$.