Score : $600$ points

问题描述

我们有 $N$ 张卡片排成一行放在桌子上。对于每个 $i = 1, 2, \ldots, N$，第 $i$ 张卡片正面写有一个整数 $A_i$，背面写有一个整数 $B_i$。最初，每张卡片都被面朝上放置。

高桥将会选择任意数量他喜欢的卡片（可能为零）并将它们翻转。然后，如果满足以下条件，他将会很开心：

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

确定是否有可能让高桥变得开心。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 09:25:22