AT_abc210_f [ABC210F] Coprime Solitaire

题目描述

桌子上排放着 $N$ 张卡片。对于 $i = 1, 2, \ldots, N$，第 $i$ 张卡片的正面写有整数 $A_i$，反面写有整数 $B_i$。
一开始，所有卡片都正面朝上。

高桥君可以任选若干张（也可以一张都不选）卡片翻面。操作后，若满足以下条件，高桥君就会感到高兴：

• 对于任意满足 $1 \leq i < j \leq N$ 的整数对 $(i, j)$，第 $i$ 张卡片和第 $j$ 张卡片当前可见面上的整数互质。

请判断高桥君是否有可能感到高兴。

输入格式

输入按以下格式从标准输入读入。

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

如果高桥君有可能感到高兴，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

3
2 5
10 9
4 8

输出 #1

Yes

输入输出样例 #2

输入 #2

2
10 100
1000 10000

输出 #2

No

说明/提示

限制

• $1 \leq N \leq 3 \times 10^4$
• $1 \leq A_i, B_i \leq 2 \times 10^6$
• 输入均为整数

样例解释 1

初始可见的整数为 $2, 10, 4$。将第 1 张和第 2 张卡片翻面后，可见的整数为 $5, 9, 4$，此时高桥君会感到高兴。因此输出 Yes。

样例解释 2

无论如何翻转卡片，高桥君都无法感到高兴。因此输出 No。

由 ChatGPT 4.1 翻译