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

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import deque

    
    
    
    def SCC(adj, adj_rev):
        N = len(adj) - 1
        seen = [0] * (N + 1)
        compressed = [0] * (N + 1)
        order = []

        for v0 in range(1, N + 1):
            if seen[v0]:
                continue
            st = deque()
            st.append(v0)
            while st:
                v = st.pop()
                if v < 0:
                    order.append(-v)
                else:
                    if seen[v]:
                        continue
                    seen[v] = 1
                    st.append(-v)
                    for u in adj[v]:
                        st.append(u)

        seen = [0] * (N + 1)
        num = 0
        for v0 in reversed(order):
            if seen[v0]:
                continue
            num += 1
            st = deque()
            st.append(v0)
            seen[v0] = 1
            compressed[v0] = num
            while st:
                v = st.pop()
                for u in adj_rev[v]:
                    if seen[u]:
                        continue
                    seen[u] = 1
                    compressed[u] = num
                    st.append(u)

        return num, compressed

    
    
    def construct(adj, num, compressed):
        N = len(adj) - 1
        adj_compressed = [set() for _ in range(num + 1)]
        for v in range(1, N + 1):
            v_cmp = compressed[v]
            for u in adj[v]:
                u_cmp = compressed[u]
                if v_cmp != u_cmp:
                    adj_compressed[v_cmp].add(u_cmp)
        return adj_compressed

    class TwoSat:
        def __init__(self, N):
            self.N = N
            self.adj = [[] for _ in range(2 * N + 1)]
            self.adj_rev = [[] for _ in range(2 * N + 1)]
            self.compressed = None

        
        
        def add_clause(self, a, a_bool, b, b_bool):
            if not a_bool:
                a += self.N
            if not b_bool:
                b += self.N
            if a <= self.N:
                self.adj[a + self.N].append(b)
                self.adj_rev[b].append(a + self.N)
            else:
                self.adj[a - self.N].append(b)
                self.adj_rev[b].append(a - self.N)
            if b <= self.N:
                self.adj[b + self.N].append(a)
                self.adj_rev[a].append(b + self.N)
            else:
                self.adj[b - self.N].append(a)
                self.adj_rev[a].append(b - self.N)

        def satisfiable(self):
            _, self.compressed = SCC(self.adj, self.adj_rev)
            for i in range(1, self.N + 1):
                if self.compressed[i] == self.compressed[i + self.N]:
                    return False
            return True

        
        
        def answer(self):
            assert self.compressed is not None
            ret = [True] * (self.N + 1)
            for i in range(1, self.N + 1):
                if self.compressed[i] < self.compressed[i + self.N]:
                    ret[i] = False
            return ret

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

    TS = TwoSat(N)
    for i in range(N):
        for j in range(i+1, N):
            if abs(X[i] - X[j]) < D:
                TS.add_clause(i+1, 0, j+1, 0)
            if abs(X[i] - Y[j]) < D:
                TS.add_clause(i+1, 0, j+1, 1)
            if abs(Y[i] - X[j]) < D:
                TS.add_clause(i+1, 1, j+1, 0)
            if abs(Y[i] - Y[j]) < D:
                TS.add_clause(i+1, 1, j+1, 1)
    ok = TS.satisfiable()
    if not ok:
        print("No")
    else:
        print("Yes")
        ans = TS.answer()
        for i in range(N):
            if ans[i+1]:
                print(X[i])
            else:
                print(Y[i])


if __name__ == '__main__':
    main()

Solution (Python):
code = r"""


from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/twosat>" namespace "atcoder" nogil:
    cdef cppclass two_sat:
        two_sat(int n)
        void add_clause(int i, bool f, int j, bool g)
        bool satisfiable()
        vector[bool] answer()
from libcpp.pair cimport pair
from libc.stdlib cimport abs
from libc.stdio cimport getchar, printf
cdef int read() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: return c
        c = c * 10 + b
cdef int n = read(), d = read(), i, j
cdef two_sat *ts = new two_sat(n)
cdef vector[pair[int, int]] z = vector[pair[int, int]](n)
cdef vector[bool] res
for i in range(n):
    z[i].first = read()
    z[i].second = read()
for i in range(n):
    for j in range(i + 1, n):
        if abs(z[i].first - z[j].first) < d: ts.add_clause(i, True, j, True)
        if abs(z[i].first - z[j].second) < d: ts.add_clause(i, True, j, False)
        if abs(z[i].second - z[j].first) < d: ts.add_clause(i, False, j, True)
        if abs(z[i].second - z[j].second) < d: ts.add_clause(i, False, j, False)
if ts.satisfiable():
    printf('Yes\n')
    res = ts.answer()
    for i in range(n):
        if res[i]: printf('%d\n', z[i].second)
        else: printf('%d\n', z[i].first)
else:
    printf('No\n')
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Solution (Python):
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):
        
        self.n = n
        self.to = [[] for _ in range(n*2)]
        self.ot = [[] for _ in range(n*2)]
        self.vals = []

    
    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)

    
    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")

Solution (Python):
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):
        
        self.n = n
        self.to = [[] for _ in range(n*2)]
        self.ot = [[] for _ in range(n*2)]
        self.vals = []

    
    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)

    
    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")

Solution (Python):
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]} 
        self.adjacent_in={(v,b):set() for v in variable for b in [True,False]} 
        

    
    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

            
            self.adjacent_out[(X,not F)].add((Y,G))
            self.adjacent_in[(Y,G)].add((X,not 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))) 
for i in range(N):
    for j in range(i+1,N):
        
        if abs(X[i]-X[j])<D:
            T.add_clause(i,False,j,False)
        
        if abs(X[i]-Y[j])<D:
            T.add_clause(i,False,j,True)

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

        
        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)))