Open Communication

## 题目描述 有两个玩家各拥有一对 $1$ 到 $9$ 的数，其中有且只有一个数是两对中都有的。他们想要通过聊天频道来找出这个数字，然而为了不让你知道，他们可能还会告诉对方自己不拥有的一对数，但这也可能导致他们自己也弄不清楚了。 现在请你根据他们的聊天信息判断，两个玩家拥有的一对数中，哪个数是两对中都有的。如果你能确定一定是它，输出这个数。如果你无法确定一定是它，但是你能确保玩家一定知道，输出 $0$ 。如果连玩家都不知道，输出 $-1$ 。 ## 输入格式 第 $1$ 行，有 $2$ 个整数，分别表示第一个玩家会告诉对方 $n$ 对数，第二个玩家会告诉对方 $m$ 对数。 （数据范围： $1 \leqslant n,\ m \leqslant 12$ ） 第 $2$ 行，有 $n$ 对取值为 $1$ 到 $9$ 的整数，表示第一个玩家告诉对方的数对，其中一定包含他自己拥有的数对。 第 $2$ 行，有 $m$ 对取值为 $1$ 到 $9$ 的整数，表示第二个玩家告诉对方的数对，其中一定包含他自己拥有的数对。 所有数对中，如果出现了 $(x,\ y)$ 且 $x \neq y$ ，则一定不会出现 $(y,\ x)$ 。 ##输出格式 输出你判断的结果。 ##提示与说明 - 第 $1$ 组样例的解释： 从第一个玩家告诉的 $(3,\ 4)$ ，第二个玩家也告诉的 $(3,\ 4)$ 中，由于两对数中有两个数字相同，故他们无法判断。 从第一个玩家告诉的 $(1,\ 2)$ ，第二个玩家告诉的 $(3,\ 4)$ 中，由于两对数中没有数字相同，故他们也无法判断。 从第一个玩家告诉的 $(3,\ 4)$ ，第二个玩家告诉的 $(1,\ 5)$ 中，理由同上。 但是从第一个玩家告诉的 $(1,\ 2)$ ，第二个玩家告诉的 $(1,\ 5)$ 中，他们就能猜测出这个数字是 $1$ ，当然你也能判断出。 因此输出 $1$ 。 - 第 $2$ 组样例的解释： 不同于上一组样例，从第一个玩家告诉的 $(1,\ 2)$ ，第二个玩家告诉的 $(1,\ 5)$ 中，他们可能会猜测出这个数字是 $1$ ，因为还有一种可能，就是从第一个玩家告诉的 $(3,\ 4)$ ，第二个玩家告诉的 $(6,\ 4)$ 中，他们也有可能会猜测这个数字是 $4$ 。尽管你无法作判断，但由于玩家们知道自己告诉对方的是不是自己拥有的数对，设想一下，如果第一个玩家拥有的数对就是 $(1,\ 2)$ ，那么第二个玩家拥有的数对肯定是 $(1,\ 5)$ 。因此，玩家一定会知道，但你并不知道，输出 $0$ 。 - 第 $3$ 组样例的解释： 这一组样例与上一组区分开来的是，这次连玩家都不知道了。原因是第一个玩家告诉对方 $(1,\ 2)$ 时，第二个玩家会导致矛盾。 先看第二个玩家告诉的 $(1,\ 3)$ ，相同的数是 $1$ ，但是再看第二个玩家告诉的 $(2,\ 3)$ ，相同的数是 $2$ 。首先你是肯定无法判断了，同时第一个玩家也无法判断，因为通过观察，第一个玩家拥有的数对一定是 $(1,\ 2)$ ，但相同的数刚好组成了这个数对。相反地，第二个玩家却知道，他也像你能观察出第一个玩家拥有的数对一定是 $(1,\ 2)$ ，同时他还知道自己拥有的数对，两个信息结合在一起，就可以从 $1$ 和 $2$ 中判断出。因此输出 $-1$ 。 感谢@Sooke 提供翻译

Two participants are each given a pair of distinct numbers from 1 to 9 such that there's exactly one number that is present in both pairs. They want to figure out the number that matches by using a communication channel you have access to without revealing it to you. Both participants communicated to each other a set of pairs of numbers, that includes the pair given to them. Each pair in the communicated sets comprises two different numbers. Determine if you can with certainty deduce the common number, or if you can determine with certainty that both participants know the number but you do not.

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 12 $ ) — the number of pairs the first participant communicated to the second and vice versa. The second line contains $ n $ pairs of integers, each between $ 1 $ and $ 9 $ , — pairs of numbers communicated from first participant to the second. The third line contains $ m $ pairs of integers, each between $ 1 $ and $ 9 $ , — pairs of numbers communicated from the second participant to the first. All pairs within each set are distinct (in particular, if there is a pair $ (1,2) $ , there will be no pair $ (2,1) $ within the same set), and no pair contains the same number twice. It is guaranteed that the two sets do not contradict the statements, in other words, there is pair from the first set and a pair from the second set that share exactly one number.

If you can deduce the shared number with certainty, print that number. If you can with certainty deduce that both participants know the shared number, but you do not know it, print $ 0 $ . Otherwise print $ -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

In the first example the first participant communicated pairs $ (1,2) $ and $ (3,4) $ , and the second communicated $ (1,5) $ , $ (3,4) $ . Since we know that the actual pairs they received share exactly one number, it can't be that they both have $ (3,4) $ . Thus, the first participant has $ (1,2) $ and the second has $ (1,5) $ , and at this point you already know the shared number is $ 1 $ . In the second example either the first participant has $ (1,2) $ and the second has $ (1,5) $ , or the first has $ (3,4) $ and the second has $ (6,4) $ . In the first case both of them know the shared number is $ 1 $ , in the second case both of them know the shared number is $ 4 $ . You don't have enough information to tell $ 1 $ and $ 4 $ apart. In the third case if the first participant was given $ (1,2) $ , they don't know what the shared number is, since from their perspective the second participant might have been given either $ (1,3) $ , in which case the shared number is $ 1 $ , or $ (2,3) $ , in which case the shared number is $ 2 $ . While the second participant does know the number with certainty, neither you nor the first participant do, so the output is $ -1 $ .