{"raw_statement":[{"iden":"statement","content":"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.\n\nBoth 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.\n\nDetermine 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."},{"iden":"input","content":"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.\n\nThe second line contains $n$ pairs of integers, each between $1$ and $9$, — pairs of numbers communicated from first participant to the second.\n\nThe third line contains $m$ pairs of integers, each between $1$ and $9$, — pairs of numbers communicated from the second participant to the first.\n\nAll 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.\n\nIt 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."},{"iden":"output","content":"If you can deduce the shared number with certainty, print that number.\n\nIf you can with certainty deduce that both participants know the shared number, but you do not know it, print $0$.\n\nOtherwise print $-1$."},{"iden":"examples","content":"Input\n\n2 2\n1 2 3 4\n1 5 3 4\n\nOutput\n\n1\n\nInput\n\n2 2\n1 2 3 4\n1 5 6 4\n\nOutput\n\n0\n\nInput\n\n2 3\n1 2 4 5\n1 2 1 3 2 3\n\nOutput\n\n\\-1"},{"iden":"note","content":"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$.\n\nIn 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.\n\nIn 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$."}],"translated_statement":[{"iden":"statement","content":"两名参与者各自获得一对从 1 到 9 的不同数字，且这两对数字中恰好有一个数字是共同的。他们希望通过你能够访问的通信渠道互相传递信息，从而推断出这个共同的数字，但又不让你得知它。\n\n两名参与者各自向对方传递了一组数字对，其中包含他们实际获得的那一对。每个传递的数字对都由两个不同的数字组成。\n\n请判断：你是否能确定地推断出这个共同的数字；或者你是否能确定地推断出两名参与者都知道这个数字，但你却不知道。\n\n第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 12$) —— 第一名参与者传递给第二名的数字对数量，以及第二名参与者传递给第一名的数字对数量。\n\n第二行包含 $n$ 个整数对，每个整数介于 $1$ 和 $9$ 之间，表示第一名参与者传递给第二名的数字对。\n\n第三行包含 $m$ 个整数对，每个整数介于 $1$ 和 $9$ 之间，表示第二名参与者传递给第一名的数字对。\n\n每个集合内的所有数字对都是互不相同的（特别地，如果存在数字对 $(1, 2)$，则同一集合中不会出现 $(2, 1)$），且每个数字对中不包含重复数字。\n\n保证两个集合与题意不矛盾，即存在一个来自第一集合的数字对和一个来自第二集合的数字对，它们恰好共享一个数字。\n\n如果你能确定地推断出共享的数字，请输出该数字。\n\n如果你能确定地推断出两名参与者都知道共享的数字，但你自己不知道，请输出 $0$。\n\n否则，请输出 $-1$。\n\n在第一个例子中，第一名参与者传递了数字对 $(1, 2)$ 和 $(3, 4)$，第二名参与者传递了 $(1, 5)$ 和 $(3, 4)$。由于我们知道他们实际获得的数字对恰好共享一个数字，因此他们不可能都拥有 $(3, 4)$。因此，第一名参与者拥有 $(1, 2)$，第二名参与者拥有 $(1, 5)$，此时你已经知道共享的数字是 $1$。\n\n在第二个例子中，要么第一名参与者拥有 $(1, 2)$ 且第二名拥有 $(1, 5)$，要么第一名拥有 $(3, 4)$ 且第二名拥有 $(6, 4)$。在第一种情况下，两人都知道共享数字是 $1$；在第二种情况下，两人都知道共享数字是 $4$。你没有足够的信息区分 $1$ 和 $4$。\n\n在第三个例子中，如果第一名参与者获得的是 $(1, 2)$，那么他们无法确定共享数字是什么，因为从他们的视角看，第二名参与者可能获得的是 $(1, 3)$（此时共享数字是 $1$），也可能获得的是 $(2, 3)$（此时共享数字是 $2$）。虽然第二名参与者能确定地知道数字，但你和第一名参与者都无法确定，因此输出 $-1$。"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 12$) —— 第一名参与者传递给第二名的数字对数量，以及第二名参与者传递给第一名的数字对数量。第二行包含 $n$ 个整数对，每个整数介于 $1$ 和 $9$ 之间，表示第一名参与者传递给第二名的数字对。第三行包含 $m$ 个整数对，每个整数介于 $1$ 和 $9$ 之间，表示第二名参与者传递给第一名的数字对。所有数字对在每个集合内互不相同（特别地，如果存在数字对 $(1, 2)$，则同一集合中不会出现 $(2, 1)$），且每个数字对中不包含重复数字。保证两个集合与题意不矛盾，即存在一个来自第一集合的数字对和一个来自第二集合的数字对，它们恰好共享一个数字。"},{"iden":"output","content":"如果你能确定地推断出共享的数字，请输出该数字。如果你能确定地推断出两名参与者都知道共享的数字，但你自己不知道，请输出 $0$。否则，请输出 $-1$。"},{"iden":"examples","content":"输入\n2 2\n1 2 3 4\n1 5 3 4\n输出\n1\n\n输入\n2 2\n1 2 3 4\n1 5 6 4\n输出\n0\n\n输入\n2 3\n1 2 4 5\n1 2 1 3 2 3\n输出\n-1"},{"iden":"note","content":"在第一个例子中，第一名参与者传递了数字对 $(1, 2)$ 和 $(3, 4)$，第二名参与者传递了 $(1, 5)$ 和 $(3, 4)$。由于我们知道他们实际获得的数字对恰好共享一个数字，因此他们不可能都拥有 $(3, 4)$。因此，第一名参与者拥有 $(1, 2)$，第二名参与者拥有 $(1, 5)$，此时你已经知道共享的数字是 $1$。\n\n在第二个例子中，要么第一名参与者拥有 $(1, 2)$ 且第二名拥有 $(1, 5)$，要么第一名拥有 $(3, 4)$ 且第二名拥有 $(6, 4)$。在第一种情况下，两人都知道共享数字是 $1$；在第二种情况下，两人都知道共享数字是 $4$。你没有足够的信息区分 $1$ 和 $4$。\n\n在第三个例子中，如果第一名参与者获得的是 $(1, 2)$，那么他们无法确定共享数字是什么，因为从他们的视角看，第二名参与者可能获得的是 $(1, 3)$（此时共享数字是 $1$），也可能获得的是 $(2, 3)$（此时共享数字是 $2$）。虽然第二名参与者能确定地知道数字，但你和第一名参与者都无法确定，因此输出 $-1$。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ A = \\{ (a_i, b_i) \\}_{i=1}^n $ be the set of pairs communicated by participant 1.  \nLet $ B = \\{ (c_j, d_j) \\}_{j=1}^m $ be the set of pairs communicated by participant 2.  \n\nLet $ P_1 \\in A $ be the actual pair held by participant 1.  \nLet $ P_2 \\in B $ be the actual pair held by participant 2.  \n\nGiven: $ |P_1 \\cap P_2| = 1 $.  \n\nDefine the set of possible common numbers:  \n$$\nS = \\{ x \\in \\{1, \\dots, 9\\} \\mid \\exists (p_1, p_2) \\in A \\times B \\text{ s.t. } p_1 \\cap p_2 = \\{x\\} \\}\n$$\n\nFor each participant, define their knowledge of the common number:\n\n- Participant 1 knows the common number **with certainty** if for their actual pair $ P_1 \\in A $, there is **exactly one** $ x \\in \\{1,\\dots,9\\} $ such that $ \\exists (c,d) \\in B $ with $ P_1 \\cap (c,d) = \\{x\\} $.  \n- Similarly for participant 2: for their actual pair $ P_2 \\in B $, there is **exactly one** $ x \\in \\{1,\\dots,9\\} $ such that $ \\exists (a,b) \\in A $ with $ P_2 \\cap (a,b) = \\{x\\} $.\n\nLet $ K_1 \\subseteq A $ be the subset of pairs in $ A $ for which participant 1 **would know** the common number (i.e., for each $ p \\in K_1 $, there is exactly one $ x $ such that $ p \\cap q = \\{x\\} $ for some $ q \\in B $).  \nSimilarly, let $ K_2 \\subseteq B $ be the subset of pairs in $ B $ for which participant 2 would know the common number.\n\nLet $ T \\subseteq A \\times B $ be the set of candidate actual pair combinations:  \n$$\nT = \\{ (p, q) \\in A \\times B \\mid |p \\cap q| = 1 \\}\n$$\n\nLet $ C = \\{ x \\mid \\exists (p,q) \\in T \\text{ s.t. } p \\cap q = \\{x\\} \\} $ — the set of possible common numbers from your perspective.\n\nLet $ T_K = \\{ (p,q) \\in T \\mid p \\in K_1 \\text{ and } q \\in K_2 \\} $ — the subset of candidate pairs where **both participants know** the common number.\n\nNow:\n\n- If $ |C| = 1 $, then **you can deduce the common number**: output the unique $ x \\in C $.\n- Else if $ T_K = T $ and $ |C| > 1 $, then **both participants know the number, but you do not**: output $ 0 $.\n- Otherwise: output $ -1 $.\n\n---\n\n**Formal Output Conditions:**\n\nLet $ C = \\{ x \\mid \\exists (p,q) \\in A \\times B, \\, p \\cap q = \\{x\\} \\} $\n\nFor each $ p \\in A $, define:  \n$ k_1(p) = \\left| \\{ x \\mid \\exists q \\in B, \\, p \\cap q = \\{x\\} \\} \\right| $\n\nFor each $ q \\in B $, define:  \n$ k_2(q) = \\left| \\{ x \\mid \\exists p \\in A, \\, p \\cap q = \\{x\\} \\} \\right| $\n\nLet $ K_1 = \\{ p \\in A \\mid k_1(p) = 1 \\} $  \nLet $ K_2 = \\{ q \\in B \\mid k_2(q) = 1 \\} $\n\nLet $ T = \\{ (p,q) \\in A \\times B \\mid |p \\cap q| = 1 \\} $\n\nLet $ T_K = \\{ (p,q) \\in T \\mid p \\in K_1 \\text{ and } q \\in K_2 \\} $\n\nThen:\n\n- If $ |C| = 1 $: output $ \\bigcup C $\n- Else if $ T_K = T $ and $ |C| > 1 $: output $ 0 $\n- Else: output $ -1 $","simple_statement":null,"has_page_source":false}