6604: AtCoder Library Practice Contest —— H - Two SAT
[Creator : ]
Description
Consider placing $N$ flags on a line. Flags are numbered through $1$ to $N$.
Flag $i$ can be placed on the coordinate $X_i$ or $Y_i$. For any two different flags, the distance between them should be at least DD.
Decide whether it is possible to place all $N$ flags. If it is possible, print such a configulation.
Flag $i$ can be placed on the coordinate $X_i$ or $Y_i$. For any two different flags, the distance between them should be at least DD.
Decide whether it is possible to place all $N$ flags. If it is possible, print such a configulation.
Input
Input is given from Standard Input in the following format:
$N\ D$
$X_1\ Y_1$
$X_2\ Y_2$
$\vdots$
$X_N\ Y_N$
$N\ D$
$X_1\ Y_1$
$X_2\ Y_2$
$\vdots$
$X_N\ Y_N$
Output
Print No if it is impossible to place $N$ flags.
If it is possible, print Yes first. After that, print $N$ lines. $i$-th line of them should contain the coodinate of flag $i$.
If it is possible, print Yes first. After that, print $N$ lines. $i$-th line of them should contain the coodinate of flag $i$.
Constraints
$1≤N≤1000$
$0 \leq D \leq 10^9$
$0 \leq X_i < Y_i \leq 10^9$
All values in Input are integer.
$0 \leq D \leq 10^9$
$0 \leq X_i < Y_i \leq 10^9$
All values in Input are integer.
Sample 1 Input
3 2
1 4
2 5
0 6
Sample 1 Output
Yes
4
2
0
Sample 2 Input
3 3
1 4
2 5
0 6
Sample 2 Output
No