407632: GYM102861 K Between Us

Ties are usually an issue on elections and games. Recently, a new game, called Between Us, was created. The game is played by a number of players over a social network. On each turn, there are multiple votings, where a player may receive only votes from friends. The player getting the largest number of votes wins the game.

The game is still in its design phase, but the game developers faced a very common issue: since the number of friends of a given player is usually small, ties are very common, which makes the game less fun. To avoid this situation, they decided to add a new module to the match-making system, where it will try to form groups of players such that each player has an odd number of friends in the same group.

This problems turned out to be more challenging than they expected and they are now focusing on a simpler variation: given a set of players, the module must find a partition of the players in at most two groups, satisfying the restriction that each player must have an odd number of friends in his group. The problem is that this partition is not always possible. Your task is to determine whether the partition is possible.

The first line of input contains two integers, $$$P$$$ and $$$F$$$, the number of players and the number of friendship relations, respectively, satisfying $$$2 \le P \le 100$$$ and $$$1 \le F \le P \times (P - 1)/2$$$. Each of the next $$$F$$$ lines will contain two integers $$$A$$$ and $$$B$$$, with $$$1 \le A, B \le P$$$ and $$$A \neq B$$$, meaning that players $$$A$$$ and $$$B$$$ are friends. Each friendship relation is given at most once, that is, if a line contains $$$A$$$ and $$$B$$$, no other line contains both numbers.

Output a single line containing one character. If the partition is possible, then write the upper case letter 'Y'; otherwise write the uppercase letter 'N'.

4 4
4 2
1 3
2 3
1 4

Y

4 3
4 2
2 3
1 2

Y

5 5
3 5
3 1
1 4
2 5
2 4

N