408950: GYM103388 H Handling the Blocks

A friend of yours invented a game and wants to know if you can solve it or if it's impossible.

He assembled a sequence of $$$N$$$ blocks. Each block has a number engraved on it and some color. All numbers are distinct and between $$$1$$$ and $$$N$$$, and different blocks can be of the same color.

The game works as follows: you can play as many turns as you want. In one turn, you choose two different blocks that share the same color and swap them.

You have to tell whether it is possible to get the entire sequence to be sorted into ascending order by numbers engraved on the blocks.

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq K \leq N$$$), representing the number of blocks in the sequence and the number of different colors, respectively.

Each of the next $$$N$$$ lines contains two integers $$$n_i$$$ and $$$c_i$$$ ($$$1 \leq n_i \leq N$$$, $$$1 \leq c_i \leq K$$$), representing the number and color of the $$$i$$$-th block, respectively.

Output one line containing one character. If the sequence can be arranged in ascending order, write the upper case letter 'Y'; otherwise write the uppercase letter 'N'.

4 2
3 1
4 2
1 1
2 2

Y

4 2
2 1
4 2
1 1
3 2

N

3 1
1 1
2 1
3 1

Y