Handling the Blocks

Interview

Time limit1sMemory limit1024 MB

Summary

Given N blocks with distinct numbers and a color each, you may swap any two blocks of the same color; decide if the blocks can be sorted by number.

Level: Medium5 of 10
Topics: Graph, Union-find, Sorting, Greedy
Solved: No attempts yet

Problem

A friend of yours invented a game and wants to know if you can solve it or if it is 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 sorted into ascending order by the numbers engraved on the blocks.

Input

The first line contains two integers N and K (1 ≤ N ≤ 105, 1 ≤ K ≤ 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 ni and ci (1 ≤ ni ≤ N, 1 ≤ ci ≤ K), representing the number and color of the i-th block, respectively.

Output

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

Examples3

Example 1
Input
```
4 2
3 1
4 2
1 1
2 2
```
Expected output
```
Y
```
Example 2
Input
```
4 2
2 1
4 2
1 1
3 2
```
Expected output
```
N
```
Example 3
Input
```
3 1
1 1
2 1
3 1
```
Expected output
```
Y
```