/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
1 以上 N 以下の相異なる整数のペア (A_i,B_i) が M 個与えられます。
1 から N の順列 P=(P_1, P_2,\ldots , P_N) であって、
任意の 1\leq i\leq M について P_{A_i}+P_{B_i} が 3 の倍数となるものが存在するか判定してください。
制約
- 2 \leq N \leq 1000
- 0 \leq M \leq \min\left( \frac{N(N-1)}{2},2\times 10^5 \right)
- 1 \leq A_i<B_i \leq N
- (A_i, B_i) は全て異なる。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 : A_M B_M
出力
問題文の条件をみたす順列が存在するならば Yes ,
そうでないならば No を出力せよ。
入力例 1
5 2 1 2 2 3
出力例 1
Yes
例えば P=(1,2,4,3,5) とすれば、 P_1+P_2=1+2=3 , P_2+P_3=2+4=6 であり、条件をみたしています。
入力例 2
3 2 1 2 2 3
出力例 2
No
順列として考えられるものは 3!=6 通りありますが、すべての条件をみたすような順列はありません。
Score : 6 points
Problem Statement
You are given M pairs (A_i,B_i) of distinct integers between 1 and N (inclusive).
Determine whether there is a permutation P=(P_1, P_2,\ldots , P_N) of the integers 1 to N such that P_{A_i}+P_{B_i} is a multiple of 3 for all 1\leq i\leq M.
Constraints
- 2 \leq N \leq 1000
- 0 \leq M \leq \min\left( \frac{N(N-1)}{2},2\times 10^5 \right)
- 1 \leq A_i<B_i \leq N
- The pairs (A_i, B_i) are all distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 : A_M B_M
Output
If there is a permutation that satisfies the conditions in the Problem Statement, print Yes;
otherwise, print No.
Sample Input 1
5 2 1 2 2 3
Sample Output 1
Yes
If we choose P=(1,2,4,3,5), for example, we have P_1+P_2=1+2=3 and P_2+P_3=2+4=6, satisfying the conditions.
Sample Input 2
3 2 1 2 2 3
Sample Output 2
No
There are 3!=6 possible permutations, but none satisfies all of the conditions.