Byteland has n cities, and at the moment has no highways. The ministry of transport has proposed to build m highways in Byteland. Proposed highway i connects cities u_i and v_i.

The king of Byteland does not necessarily want to build all of the proposed highways. Instead, he wants that every city is beautiful in the sense that it is the endpoint of an odd number of highways. Find out whether it is possible to build a subset of the proposed highways (possibly all of the proposed highways) so that every city is beautiful.

Input

The first line of the input contains two integers, n and m, the number of cities and the number of proposed highways. Next m lines each contain two integers, u_i, v_i meaning that the highway is between cities u_i and v_i.

Output

Output YAY if it is possible to build highways so that each city is incident to an odd number of highways. Otherwise output QAQ

Constraints

• 2 \le n \le 10^5
• 1 \le m \le 10^5
• 1 \le u_i, v_i \le n, u_i \neq v_i

Examples

Input:

6 7
1 3
4 1
3 4
4 5
6 4
6 2
2 3

Output:

YAY

You can build highways (1, 3), (2, 3), (3, 4), (4, 5), (4, 6)

Input:

5 4
1 3
2 4
4 5
2 5

Output:

QAQ

Input:

4 2
1 3
2 4

Output:

YAY