1 人解决，4 人已尝试。
1 份提交通过，共有 6 份提交。
9.9 EMB 奖励。
2578. Knights
单点时限: 2.0 sec
内存限制: 256 MB
//speail judge 尚未写好
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 xi and yi (1 <= xi, yi <= 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 xi^, yi^ on line i + 1, giving a destination
that Alice may choose for knight i in the first turn in order to win the game.
样例
Input
2 3 2 3 3 2 3 4 2 3 3 2 4 4
Output
YES 1 1 1 1 NO
题目标签