English · Original
Chinese · Translation
Formal · Original
Zane the wizard is going to perform a magic show shuffling the cups.
There are _n_ cups, numbered from 1 to _n_, placed along the _x_\-axis on a table that has _m_ holes on it. More precisely, cup _i_ is on the table at the position _x_ = _i_.
The problematic bone is initially at the position _x_ = 1. Zane will confuse the audience by swapping the cups _k_ times, the _i_\-th time of which involves the cups at the positions _x_ = _u__i_ and _x_ = _v__i_. If the bone happens to be at the position where there is a hole at any time, it will fall into the hole onto the ground and will not be affected by future swapping operations.
Do not forget that Zane is a wizard. When he swaps the cups, he does not move them ordinarily. Instead, he teleports the cups (along with the bone, if it is inside) to the intended positions. Therefore, for example, when he swaps the cup at _x_ = 4 and the one at _x_ = 6, they will not be at the position _x_ = 5 at any moment during the operation.
<center></center>Zane’s puppy, Inzane, is in trouble. Zane is away on his vacation, and Inzane cannot find his beloved bone, as it would be too exhausting to try opening all the cups. Inzane knows that the Codeforces community has successfully helped Zane, so he wants to see if it could help him solve his problem too. Help Inzane determine the final position of the bone.
## Input
The first line contains three integers _n_, _m_, and _k_ (2 ≤ _n_ ≤ 106, 1 ≤ _m_ ≤ _n_, 1 ≤ _k_ ≤ 3·105) — the number of cups, the number of holes on the table, and the number of swapping operations, respectively.
The second line contains _m_ **distinct** integers _h_1, _h_2, ..., _h__m_ (1 ≤ _h__i_ ≤ _n_) — the positions along the _x_\-axis where there is a hole on the table.
Each of the next _k_ lines contains two integers _u__i_ and _v__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, _u__i_ ≠ _v__i_) — the positions of the cups to be swapped.
## Output
Print one integer — the final position along the _x_\-axis of the bone.
[samples]
## Note
In the first sample, after the operations, the bone becomes at _x_ = 2, _x_ = 5, _x_ = 7, and _x_ = 1, respectively.
In the second sample, after the first operation, the bone becomes at _x_ = 2, and falls into the hole onto the ground.
Zane the wizard is going to perform a magic show shuffling the cups.
There are $n$ cups, numbered from $1$ to $n$, placed along the $x$-axis on a table that has $m$ holes on it. More precisely, cup $i$ is on the table at the position $x = i$.
The problematic bone is initially at the position $x = 1$. Zane will confuse the audience by swapping the cups $k$ times, the $i$-th time of which involves the cups at the positions $x = u_i$ and $x = v_i$. If the bone happens to be at the position where there is a hole at any time, it will fall into the hole onto the ground and will not be affected by future swapping operations.
Do not forget that Zane is a wizard. When he swaps the cups, he does not move them ordinarily. Instead, he teleports the cups (along with the bone, if it is inside) to the intended positions. Therefore, for example, when he swaps the cup at $x = 4$ and the one at $x = 6$, they will not be at the position $x = 5$ at any moment during the operation.
Zane’s puppy, Inzane, is in trouble. Zane is away on his vacation, and Inzane cannot find his beloved bone, as it would be too exhausting to try opening all the cups. Inzane knows that the Codeforces community has successfully helped Zane, so he wants to see if it could help him solve his problem too. Help Inzane determine the final position of the bone.
## Input
The first line contains three integers $n$, $m$, and $k$ ($2 ≤ n ≤ 10^6$, $1 ≤ m ≤ n$, $1 ≤ k ≤ 3·10^5$) — the number of cups, the number of holes on the table, and the number of swapping operations, respectively.
The second line contains $m$ *distinct* integers $h_1, h_2, ..., h_m$ ($1 ≤ h_i ≤ n$) — the positions along the $x$-axis where there is a hole on the table.
Each of the next $k$ lines contains two integers $u_i$ and $v_i$ ($1 ≤ u_i, v_i ≤ n$, $u_i ≠ v_i$) — the positions of the cups to be swapped.
## Output
Print one integer — the final position along the $x$-axis of the bone.
[samples]
## Note
In the first sample, after the operations, the bone becomes at $x = 2$, $x = 5$, $x = 7$, and $x = 1$, respectively.
In the second sample, after the first operation, the bone becomes at $x = 2$, and falls into the hole onto the ground.
**Definitions**
Let $ n, m, k \in \mathbb{Z}^+ $ denote the number of cups, holes, and swaps, respectively.
Let $ H = \{h_1, h_2, \dots, h_m\} \subseteq \{1, 2, \dots, n\} $ be the set of hole positions.
Let $ b_0 = 1 $ be the initial position of the bone.
Let $ S = \{(u_1, v_1), (u_2, v_2), \dots, (u_k, v_k)\} $ be the sequence of swap operations, where each $ (u_i, v_i) $ denotes swapping cups at positions $ u_i $ and $ v_i $.
**Constraints**
1. $ 2 \leq n \leq 10^6 $
2. $ 1 \leq m \leq n $
3. $ 1 \leq k \leq 3 \cdot 10^5 $
4. All $ h_i \in H $ are distinct.
5. For all $ i \in \{1, \dots, k\} $: $ 1 \leq u_i, v_i \leq n $, $ u_i \ne v_i $
**Objective**
Simulate the bone’s position $ b \in \{1, \dots, n\} $ through the sequence of swaps:
- Initialize $ b = b_0 = 1 $.
- For each swap $ (u_i, v_i) $:
- If $ b = u_i $, set $ b = v_i $.
- Else if $ b = v_i $, set $ b = u_i $.
- Else, $ b $ remains unchanged.
- If at any point $ b \in H $, the bone falls into a hole and remains there permanently (no further swaps affect it).
Output the final value of $ b $.
API Response (JSON)
{
"problem": {
"name": "B. Find The Bone",
"description": {
"content": "Zane the wizard is going to perform a magic show shuffling the cups. There are _n_ cups, numbered from 1 to _n_, placed along the _x_\\-axis on a table that has _m_ holes on it. More precisely, cup _i",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF796B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Zane the wizard is going to perform a magic show shuffling the cups.\n\nThere are _n_ cups, numbered from 1 to _n_, placed along the _x_\\-axis on a table that has _m_ holes on it. More precisely, cup _i...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Zane the wizard is going to perform a magic show shuffling the cups.\n\nThere are $n$ cups, numbered from $1$ to $n$, placed along the $x$-axis on a table that has $m$ holes on it. More precisely, cup $...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, k \\in \\mathbb{Z}^+ $ denote the number of cups, holes, and swaps, respectively. \nLet $ H = \\{h_1, h_2, \\dots, h_m\\} \\subseteq \\{1, 2, \\dots, n\\} $ be the set of hole pos...",
"is_translate": false,
"language": "Formal"
}
]
}