Двум участникам предоставили по паре чисел от 1 до 9, так что ровно одно число встречается в обеих парах. Они хотят определить, какое число в их парах совпадает, используя канал связи, к которому у вас есть доступ, так, чтобы вы не могли определить это число.
Оба участника передали друг другу множество пар чисел, которое включает пару, данную им. Каждая пара состоит из двух различных чисел.
Определите, можете ли вы однозначно определить число, которое совпадает у двух участников, или верно ли, что оба участника могут определить это число, а вы — нет.
Выходные данные
Если вы можете однозначно определить число, которое совпадает, выведите это число.
Иначе, если вы можете однозначно утверждать, что оба участника знают это число, а вы — нет, выведите \(0\).
Иначе выведите \(-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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
1 2 3 4
1 5 3 4
|
1
|
|
2
|
2 2
1 2 3 4
1 5 6 4
|
0
|
|
3
|
2 3
1 2 4 5
1 2 1 3 2 3
|
-1
|