Problem:


Score : 100 points

Problem Statement

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 D.

Decide whether it is possible to place all N flags. If it is possible, print such a configulation.

Constraints

1 \leq N \leq 1000

0 \leq D \leq 10^9

0 \leq X_i < Y_i \leq 10^9

All values in Input are integer.

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

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.

Sample Input 1

3 2
1 4
2 5
0 6

Sample Output 1

Yes
4
2
0

Sample Input 2

3 3
1 4
2 5
0 6

Sample Output 2

No



Sample input:
3 2
1 4
2 5
0 6


Sample output:
Yes
4
2
0

Submission status: Accepted

Solution code:
from operator import itemgetter
from itertools import *
from bisect import *
from collections import *
from heapq import *
import sys

sys.setrecursionlimit(10**6)

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
int1 = lambda x: int(x)-1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def SCC(to, ot):
    n = len(to)

    def dfs(u):
        for v in to[u]:
            if com[v]: continue
            com[v] = 1
            dfs(v)
        top.append(u)

    top = []
    com = [0]*n
    for u in range(n):
        if com[u]: continue
        com[u] = 1
        dfs(u)

    def rdfs(u, k):
        for v in ot[u]:
            if com[v] != -1: continue
            com[v] = k
            rdfs(v, k)

    com = [-1]*n
    k = 0
    for u in top[::-1]:
        if com[u] != -1: continue
        com[u] = k
        rdfs(u, k)
        k += 1

    return k, com

class TwoSat:
    def __init__(self, n):
        # to[v][u]...頂点uの値がvのときの遷移先と反転の有無
        self.n = n
        self.to = [[] for _ in range(n*2)]
        self.ot = [[] for _ in range(n*2)]
        self.vals = []

    # uがu_val(0 or 1)ならばvはv_val(0 or 1)
    def add_edge(self, u, u_val, v, v_val):
        self.to[u*2+u_val].append(v*2+v_val)
        self.ot[v*2+v_val].append(u*2+u_val)

    # 条件を満たすかどうかをboolで返す。構成はself.valsに入る
    def satisfy(self):
        k, com = SCC(self.to, self.ot)
        for u in range(self.n):
            if com[u*2]==com[u*2+1]:return False
            self.vals.append(com[u*2]<com[u*2+1])
        return True

n, d = MI()
xy = LLI(n)
ts = TwoSat(n)

for i in range(n):
    x1, y1 = xy[i]
    for j in range(i):
        x2, y2 = xy[j]
        if abs(x1-x2) < d:
            ts.add_edge(i, 0, j, 1)
            ts.add_edge(j, 0, i, 1)
        if abs(x1-y2) < d:
            ts.add_edge(i, 0, j, 0)
            ts.add_edge(j, 1, i, 1)
        if abs(y1-x2) < d:
            ts.add_edge(i, 1, j, 1)
            ts.add_edge(j, 0, i, 0)
        if abs(y1-y2) < d:
            ts.add_edge(i, 1, j, 0)
            ts.add_edge(j, 1, i, 0)

if ts.satisfy():
    print("Yes")
    for j,xyi in zip(ts.vals,xy):print(xyi[j])
else:print("No")

Submission status: Accepted

Solution code:
class Two_SAT:
    """2-SATを定義する.

    """

    #入力定義
    def __init__(self,variable=[]):
        self.variable=set(variable)

        self.clause_number=0
        self.variable_number=len(variable)

        self.adjacent_out={(v,b):set() for v in variable for b in [True,False]} #出近傍(vが始点)
        self.adjacent_in={(v,b):set() for v in variable for b in [True,False]} #入近傍(vが終点)
        #※ (X,False)が not Xに対応

    #変数の追加
    def add_variable(self,*adder):
        """変数を加える.

        adder(可変長):加える変数の名前
        """
        for v in adder:
            if v not in self.variable:
                self.adjacent_in[(v,True)]=set()
                self.adjacent_in[(v,False)]=set()
                self.adjacent_out[(v,True)]=set()
                self.adjacent_out[(v,False)]=set()

                self.variable_number+=1
                self.variable.add(v)

    #節の追加
    def add_clause(self,X,F,Y,G):
        """(X=F) or (Y=G) という節を加える.

        X,Y:変数の名前
        F,G:真偽値(True or False)
        """

        assert isinstance(F,bool),"Fが真偽値ではない"
        assert isinstance(G,bool),"Gが真偽値ではない"

        for v in [X,Y]:
            if v not in self.variable:
                self.add_variable(v)

        if (Y,G) not in self.adjacent_out[(X,not F)]:
            self.clause_number+=1

            #(X,not F)→(Y,G)を追加
            self.adjacent_out[(X,not F)].add((Y,G))
            self.adjacent_in[(Y,G)].add((X,not F))

            #(Y,not G) → (X,F)を追加
            self.adjacent_out[(Y,not G)].add((X,F))
            self.adjacent_in[(X,F)].add((Y,not G))

    #節を除く
    def remove_edge(self,X,F,Y,G):
        pass

    #変数を除く
    def remove_vertex(self,*vertexes):
        pass

    #変数が存在するか否か
    def variable_exist(self,v):
        """変数 X が存在するか?

        X,Y:変数の名前
        """
        return v in self.variable

    #グラフに節が存在するか否か
    def clause_exist(self,X,F,Y,G):
        """(X=F) or (Y=G) という節が存在するか?

        X,Y:変数の名前
        F,G:真偽値(True or False)
        """
        if not(self.variable_exist(X) and self.variable_exist(Y)):
            return False
        return (Y,G) in self.adjacent_out[(X,not F)]

    #近傍
    def neighbohood(self,v):
        pass

    #出次数
    def out_degree(self,v):
        pass

    #入次数
    def in_degree(self,v):
        pass

    #次数
    def degree(self,v):
        pass

    #変数の数
    def variable_count(self):
        return len(self.vertex)

    #節の数
    def clause_count(self):
        return self.edge_number

    #充足可能?
    def Is_Satisfy(self,Mode):
        """有向グラフDを強連結成分に分解

        Mode:
        0(Defalt)---充足可能?
        1        ---充足可能ならば,その変数の割当を変える.(不可能なときはNone)
        """
        import sys
        from collections import deque

        T={(x,b):-1  for b in [True,False] for x in self.variable}
        Q=deque([])

        def f(v):
            T[v]=0
            for w in self.adjacent_out[v]:
                if T[w]==-1:
                    f(w)

            Q.appendleft(v)
            T[v]=len(Q)

        x=self.variable.pop()
        self.variable.add(x)

        RT=sys.getrecursionlimit()
        sys.setrecursionlimit(3*10**5)

        for b in [True,False]:
            for v in self.variable:
                w=(v,b)
                if T[w]==-1:
                    f(w)

        sys.setrecursionlimit(RT)

        T={(x,b):-1 for b in [True,False] for x in self.variable }
        C=[]
        p=0

        for v in Q:
            if T[v]==-1:
                T[v]=p
                P=[v]
                R=deque([v])

                while R:
                    u=R.popleft()
                    for w in self.adjacent_in[u]:
                        if T[w]==-1:
                            T[w]=p
                            R.append(w)
                            P.append(w)
                C.append(P)
                p+=1


        if Mode==0:
            for x in self.variable:
                if T[(x,True)]==T[(x,False)]:
                    return False

            return True
        else:
            X={x:None for x in self.variable}
            for x in self.variable:
                if T[(x,True)]==T[(x,False)]:
                    return None
                else:
                    X[x]=(T[(x,False)]<T[(x,True)])
            return X
#================================================
N,D=map(int,input().split())
X=[0]*N
Y=[0]*N

for i in range(N):
    x,y=map(int,input().split())
    X[i]=x
    Y[i]=y

T=Two_SAT(list(range(N))) # True→Xiに建てる,False→Yiに建てる
for i in range(N):
    for j in range(i+1,N):
        #XX
        if abs(X[i]-X[j])<D:
            T.add_clause(i,False,j,False)
        #XY
        if abs(X[i]-Y[j])<D:
            T.add_clause(i,False,j,True)

        #YX
        if abs(Y[i]-X[j])<D:
            T.add_clause(i,True,j,False)

        #YY
        if abs(Y[i]-Y[j])<D:
            T.add_clause(i,True,j,True)

H=T.Is_Satisfy(Mode=1)
if H==None:
    print("No")
else:
    Z=[0]*N
    for i in range(N):
        if H[i]:
            Z[i]=X[i]
        else:
            Z[i]=Y[i]

    print("Yes")
    print("\n".join(map(str,Z)))