← 返回题目列表

AtCoder · practice2_h

H. 两次SAT

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

考虑放置 N 一行上的标志。标志的编号通过 1 to N.

标志 i 可以放置在坐标上 X_i or Y_i。 对于任何两个不同的标志,它们之间的距离应至少为 D.

决定是否可以将所有 N 标志。如果可能的话,打印这样的配置。

约束

  • 1 \leq N \leq 1000
  • 0 \leq D \leq 10^9
  • 0 \leq X_i < Y_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N D
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

输出

打印 No 如果无法放置 N 标志。

如果可能,请打印 Yes 首先。 之后,打印 N 行。 i- 第行应包含标志的坐标 i.


示例输入 1

3 2
1 4
2 5
0 6

示例输出 1

Yes
4
2
0

示例输入 2

3 3
1 4
2 5
0 6

示例输出 2

No