/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
テーブルの上に N 枚のカードが並んでいます。
i = 1, 2, \ldots, N について、i 枚目のカードの表には整数 A_i が、裏には整数 B_i が書かれています。
はじめ、すべてのカードは表が見えるように置かれています。
高橋君は好きな枚数（ 0 枚でも良い）のカードを選んで裏返します。 その結果、以下の条件が満たされれば高橋君はうれしい気持ちになります。
- 1 \leq i \lt 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 です。
1 枚目のカードと 2 枚目のカードを裏返すと、見えている整数は 5, 9, 4 となり、高橋君はうれしい気持ちになります。よって Yes を出力します。
入力例 2
2 10 100 1000 10000
出力例 2
No
どのようにカードを裏返しても、高橋君はうれしい気持ちになりません。よって No を出力します。
Score : 600 points
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.