102105: [AtCoder]ABC210 F - Coprime Solitaire

Problem Statement

We have $N$ cards arranged in a row on a table. For each $i = 1, 2, \ldots, N$, the $i$-th card has an integer $A_i$ written on the front and an integer $B_i$ written on the back. Initially, every card is placed face up.

Takahashi will choose any number of cards he likes (possibly zero) and flip them. Then, he will be happy if the following condition is satisfied:

• for every pair of integers $(i, j)$ such that $1 \leq i \lt j \leq N$, the integers visible on the $i$-th and $j$-th cards are coprime.

Determine whether it is possible for Takahashi to be happy.

Constraints

• $1 \leq N \leq 3 \times 10^4$
• $1 \leq A_i, B_i \leq 2 \times 10^6$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

If it is possible for Takahashi to be happy, print Yes; otherwise, print No.

Sample Input 1

3
2 5
10 9
4 8

Sample Output 1

Yes

Initially, we see integers $2$, $10$, and $4$. If we flip the first and second cards, we will see $5$, $9$, and $4$, which will make Takahashi happy. Thus, we should print Yes.

Sample Input 2

2
10 100
1000 10000

Sample Output 2

No

There is no way to flip cards to make Takahashi happy, so we should print No.

问题描述

我们有一张桌子上排列着$N$张卡片。每张卡片的正面写有整数$A_i$，背面写有整数$B_i$。最初，所有卡片都是正面朝上。

高桥将选择任意数量的卡片（可能为零张）并翻转它们。如果满足以下条件，他将会感到高兴：

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

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

限制条件

• $1 \leq N \leq 3 \times 10^4$
• $1 \leq A_i, B_i \leq 2 \times 10^6$
• 输入中的所有值都是整数。

输入

从标准输入按以下格式获取输入：

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

输出

如果高桥有可能感到高兴，打印Yes；否则，打印No。

样例输入1

3
2 5
10 9
4 8

样例输出1

Yes

最初，我们看到整数$2$，$10$和$4$。如果我们翻转第一张和第二张卡片，我们将看到$5$，$9$和$4$，这将使高桥感到高兴。因此，我们应该打印Yes。

样例输入2

2
10 100
1000 10000

样例输出2

No

无法翻转卡片以使高桥感到高兴，所以我们应该打印No。