2021 软件学院 ACM 集训队筛选赛

Problem E. 重云的阵法图

重云的阵法书上记录了一个特别有意思的阵法。这个阵法是一个 n*n 的棋盘,棋盘上有多个象棋中的“马”棋子。马只有如图所示的移动方式: 即如果“马”在棋盘上的坐标是 (x,y) ,那么它在一次移动后所能到达的地方的坐标只有可能是 (x-2,y+1),(x-2,y-1),(x-1,y-2),(x+1,y-2)

另外,棋子不能移动出棋盘边界,即棋子移动后 x 坐标和 y 坐标都不能小于 1 。且棋盘最左下角格子的坐标是 (1,1)

重云将一个写字非常难看的鬼怪困在这个阵法后,重云会首先移动棋盘中的每个可以移动的“马”,然后鬼怪也会移动棋盘中的每个可以移动的“马”,如此交替操作,直到棋盘中没有马可以被移动,多个马可以重合在棋盘上的同一个位置。

当重云首先遇到没有可以移动的马的情况时,鬼怪就会逃脱,否则鬼怪就会被消灭。

重云的阵法中有太多的马了,很难计算,请你帮忙计算,如果双方都按最优情况行动,鬼怪是否一定能被消灭。如果鬼怪一定能被消灭,请给出重云第一轮该如何移动每个马使得鬼怪一定会被消灭。(题目保证每个马至少能在棋盘上行动一次,且一开始不会有马重合)

输入

第一行包括两个整数 K(1 \leq K \leq 2 \times 10^5),N(1 \leq N \leq 10^6),以空格间隔。

接下来有 K 行来描述 K 个马的位置。

i+1 行有两个整数 x_i,y_i(1 \leq x_i,y_i \leq N) ,以空格间隔,表示第 i 个马在棋盘中的坐标

输出

如果鬼怪一定能被消灭,输出“YES”,否则输出”NO”。

如果前面输出的是“YES”,接下来输出 K 行。

i+1 行输出 x_i,y_i ,表示如果要一定能消灭鬼怪,重云第一轮,第 i 个马要移动到的位置。

如果有多种移动马的方案,输出任意一种即可。

样例

标准输入 复制文本
5 5
3 5
3 2
2 3
2 4
4 5
标准输出 复制文本
YES
1 4
1 1
1 1
1 2
5 3

登录以提交代码。
单点时限 2 秒
内存限制 128 MB
提交 4
通过 1

A B C D E F G H

现在已经封榜。
因为过题情况不理想,所以给点提示:A、E、F题是模板题,不知道对应模板的同学可以尝试其他题目。
F题的输出描述更准确了
B题测试样例出错,已修改
F题测试样例格式出错,已修改