Problem Description

Given \( M \) pairs of distinct integers \( (A_i, B_i) \) between \( 1 \) and \( N \), determine if there exists a permutation \( P = (P_1, P_2, \ldots, P_N) \) of the numbers from \( 1 \) to \( N \) such that for every \( 1 \leq i \leq M \), \( P_{A_i} + P_{B_i} \) is a multiple of \( 3 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( M \) \( A_1 \) \( B_1 \) \( : \) \( A_M \) \( B_M \)

Output Format

Output Yes if there exists a permutation satisfying the conditions of the problem, otherwise output No.

Sample Input and Output

Sample Input #1

5 2
1 2
2 3

Sample Output #1

Yes

Sample Input #2

3 2
1 2
2 3

Sample Output #2

No

Notes/Hints

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 \)
• All pairs \( (A_i, B_i) \) are distinct.
• All inputs are integers.

Sample Explanation 1

For example, if \( P = (1, 2, 4, 3, 5) \), then \( P_1 + P_2 = 1 + 2 = 3 \) and \( P_2 + P_3 = 2 + 4 = 6 \), satisfying the conditions.

Sample Explanation 2

There are \( 3! = 6 \) possible permutations, but none of them satisfy all the conditions.

见题面 Input 部分

见题面 Output 部分