3326번 - Knights 스페셜 저지다국어

Alice and Bob are playing a game. Initially K black Knights are placed on a N × N chessboard. Now the players take turns. On each turn, a player moves every knight that has at least one valid move left. The following four moves are valid, as long as they do not move the knight off the board:

A knight with no valid moves left remains at its current position. The first player who is not able to move any of the knights loses the game. Note that during the game several knights are allowed to occupy the same square.

You are given the locations of the knights on the chessboard. Alice begins the game. Determine whether she can win the game, assuming that both players play optimally. If she can win, output a possible first move for each knight. In the beginning, there is at least one valid move for each knight, and no two knights are placed on the same square of the chessboard.

The first line contains the two integers K (1 ≤ K ≤ 200 000) and N (1 ≤ N ≤ 1 000 000) separated by a single space. This line is followed by K lines describing the positions of the knights.

Line i + 1 contains two integers x_i and y_i (1 ≤ x_i, y_i ≤ N) separated by a single space, the coordinates of knight i.

Output a single line containing the word NO if Alice cannot win the game. Otherwise, output K + 1 lines with YES on the first line and coordinates x'_i , y'_i on line i + 1, giving a destination that Alice may choose for knight i in the first turn in order to win the game.