互质卡片

题目描述

桌面上有 $N$ 张牌排成一排。 对于每个 $i = 1, 2, \ldots, N$,第 $i$ 张牌的正面写着整数 $A_i$,背面写着整数 $B_i$。 初始时,所有牌正面朝上。

高桥君可以选择任意张数(可以为 0 张)的牌并翻转。 然后,如果满足以下条件,他就会很高兴:

对于满足 $1 \le i \lt j \le N$ 的每一对整数 $(i, j)$,第 $i$ 张和第 $j$ 张牌上可见的整数互质。

判断高桥君是否可能变得高兴。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

如果高桥君可能变得高兴,输出 Yes;否则输出 No。

样例

3
2 5
10 9
4 8

Yes

初始时,我们看到整数 $2$、$10$ 和 $4$。 如果翻转第一张和第二张牌,将看到 $5$、$9$ 和 $4$,高桥君会变得高兴。因此,应输出 Yes。

2
10 100
1000 10000

No

无论如何翻牌都无法使高桥君变得高兴,因此应输出 No。

数据范围

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