两名参与者分别获得一对从 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$$$。