← 返回题目列表

Codeforces · 993/B

B. 开放式通讯

中文机器翻译题面 查看原题

两名参与者分别获得一对从 1 到 9 的不同数字,以便两对中都出现一个数字。他们希望通过使用您有权访问的通信渠道来找出匹配的号码,而不向您透露。

两个参与者互相传达了一组数字对,其中包括给他们的数字对。所传送的组中的每一对包括两个不同的数字。

确定您是否可以确定地推断出公共数字,或者您是否可以确定两个参与者都知道该数字但您不知道。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 12$$$) — 第一个参与者与第二个参与者通信的对数,反之亦然。

第二行包含 $$$n$$$ 整数对,每个整数在 $$$1$$$ 和 $$$9$$$ 之间, — 从第一个参与者传递给第二个参与者的数字对。

第三行包含 $$$m$$$ 整数对,每个整数在 $$$1$$$ 和 $$$9$$$ 之间, — 从第二个参与者传递给第一个参与者的数字对。

每个集合中的所有对都是不同的(特别是,如果有一对 $$$(1,2)$$$,则同一集合中不会有对 $$$(2,1)$$$),并且没有对包含两次相同的数字。

保证这两个集合与陈述不矛盾,换句话说,第一组中的一对和第二组中的一对恰好共享一个数字。

输出

如果您可以确定地推断出共享数字,请打印该数字。

如果您可以肯定地推断出两个参与者都知道共享号码,但您不知道,请打印 $$$0$$$。

否则打印$$$-1$$$。

示例

输入 #1

2 2
1 2 3 4
1 5 3 4

输出 #1

1

输入 #2

2 2
1 2 3 4
1 5 6 4

输出 #2

0

输入 #3

2 3
1 2 4 5
1 2 1 3 2 3

输出 #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$$$。