English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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$.
[samples]
## Note
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$.
两名参与者各自获得一对从 1 到 9 的不同数字，且这两对数字中恰好有一个数字是共同的。他们希望通过你可访问的通信渠道互相传递信息，以确定这个共同的数字，但又不向你透露它。
两名参与者各自向对方发送了一组数字对，其中包含了他们实际获得的那一对。每个传递的数字对都由两个不同的数字组成。
请判断你是否能确定地推断出这个共同的数字，或者是否能确定地推断出两名参与者都知道这个数字，而你却不知道。
第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 12$) —— 第一名参与者发送给第二名的数字对数量和第二名发送给第一名的数字对数量。
第二行包含 $n$ 对整数，每对介于 $1$ 到 $9$ 之间，表示第一名参与者发送给第二名的数字对。
第三行包含 $m$ 对整数，每对介于 $1$ 到 $9$ 之间，表示第二名参与者发送给第一名的数字对。
每个集合内的所有数字对互不相同（特别地，如果存在数字对 $(1, 2)$，则同一集合中不会出现 $(2, 1)$），且每个数字对中不包含重复数字。
保证两个集合与题意不矛盾，即存在一个来自第一集合的数字对和一个来自第二集合的数字对，它们恰好共享一个数字。
如果你能确定地推断出共享的数字，请输出该数字。
如果你能确定地推断出两名参与者都知道共享的数字，而你自己不知道，请输出 $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$。
## Input
第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n, m lt.eq 12$) —— 第一名参与者发送给第二名的数字对数量和第二名发送给第一名的数字对数量。第二行包含 $n$ 对整数，每对介于 $1$ 到 $9$ 之间，表示第一名参与者发送给第二名的数字对。第三行包含 $m$ 对整数，每对介于 $1$ 到 $9$ 之间，表示第二名参与者发送给第一名的数字对。所有数字对在各自集合内互不相同（特别地，如果存在数字对 $(1, 2)$，则同一集合中不会出现 $(2, 1)$），且每个数字对中不包含重复数字。保证两个集合与题意不矛盾，即存在一个来自第一集合的数字对和一个来自第二集合的数字对，它们恰好共享一个数字。
## Output
如果你能确定地推断出共享的数字，请输出该数字。如果你能确定地推断出两名参与者都知道共享的数字，而你自己不知道，请输出 $0$。否则输出 $-1$。
[samples]
## Note
在第一个例子中，第一名参与者发送了数字对 $(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$。
Let $ A = \{ (a_i, b_i) \}_{i=1}^n $ be the set of pairs communicated by participant 1.
Let $ B = \{ (c_j, d_j) \}_{j=1}^m $ be the set of pairs communicated by participant 2.
Let $ S \subseteq A \times B $ be the set of all pairs $ (p, q) \in A \times B $ such that $ |p \cap q| = 1 $.
This represents all consistent assignments of actual pairs to the two participants, given the constraint that their true pairs share exactly one number.
Let $ C = \bigcup_{(p,q) \in S} (p \cap q) $ be the set of all possible common numbers across all consistent assignments.
Let $ K_1 = \{ x \in \mathbb{Z} \mid \exists! (p,q) \in S \text{ such that } x = p \cap q \text{ and } p \text{ is fixed} \} $ — the set of numbers that participant 1 can deduce as the common number, given their own pair.
Similarly, $ K_2 $ for participant 2.
But since we do not know which pair each participant holds, we define:
For each $ p \in A $, let $ \text{PossibleCommons}(p) = \{ x \mid \exists q \in B \text{ such that } |p \cap q| = 1 \text{ and } p \cap q = \{x\} \} $.
Then participant 1 knows the common number if and only if $ |\text{PossibleCommons}(p)| = 1 $ for their actual $ p $.
Similarly for participant 2.
Define:
- $ D = \{ x \in \mathbb{N} \mid \exists (p,q) \in S \text{ such that } p \cap q = \{x\} \} $ — possible common numbers from your perspective.
- $ K = \{ x \in \mathbb{N} \mid \forall (p,q) \in S \text{ with } p \cap q = \{x\}, \text{ we have } |\text{PossibleCommons}(p)| = 1 \text{ and } |\text{PossibleCommons}(q)| = 1 \} $ — common numbers such that both participants can deduce them.
Then:
- If $ |D| = 1 $, output the unique element of $ D $.
- Else if $ D \subseteq K $ and $ |D| \geq 2 $, output $ 0 $.
- Otherwise, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "D. Open Communication",
"description": {
"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 co",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF994D"
},
"statements": [
{
"statement_type": "Markdown",
"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 co...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "两名参与者各自获得一对从 1 到 9 的不同数字，且这两对数字中恰好有一个数字是共同的。他们希望通过你可访问的通信渠道互相传递信息，以确定这个共同的数字，但又不向你透露它。\n\n两名参与者各自向对方发送了一组数字对，其中包含了他们实际获得的那一对。每个传递的数字对都由两个不同的数字组成。\n\n请判断你是否能确定地推断出这个共同的数字，或者是否能确定地推断出两名参与者都知道这个数字，而你却不知道。\n\n第...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "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 $ S \\subseteq A...",
"is_translate": false,
"language": "Formal"
}
]
}