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):
import sys
input = sys.stdin.readline
n, d = map(int,input().split())
C = [list(map(int,input().split())) for i in range(n)]

def dfs_numbering(st, M, V, ANS, cnt, v):
    ST = [st]
    while len(ST) > 0:
        i = ST[-1]
        if ANS[i] == -1:
            V[i] = v
            end = 1
            for x in M[i]:
                if V[x] == -1:
                    ST.append(x)
                    end = 0
            if end == 1:
                ST.pop()
                ANS[i] = cnt
                cnt += 1
        else:
            ST.pop()
    return cnt

class scc():  
    def __init__(self, n):  
        self.n = n
        self.M = [[] for i in range(n)]
        self.IM = [[] for i in range(n)]

    def add_edge(self, frm, to):  
        self.M[frm].append(to)
        self.IM[to].append(frm)

    def scc_list(self):  
        n = self.n
        V = [-1] * n
        ANS = [-1] * n

        cnt = 0
        for i in range(n):
            if V[i] == -1:
                cnt = dfs_numbering(i, self.M, V, ANS, cnt, 0)

        ANS1 = [[ANS[i], i] for i in range(n)]
        ANS1.sort(reverse=True)

        V = [-1] * n
        ANS = [-1] * n
        v = 0
        for i in range(n):
            if V[ANS1[i][1]] == -1:
                dfs_numbering(ANS1[i][1], self.IM, V, ANS, 0, v)
                v += 1

        FANS = [[] for i in range(v)]
        for i in range(n):
            FANS[V[i]].append(i)

        return FANS

class twosat():
    def __init__(self, n):
        self.n = n
        self.S = scc(2*n)
        self.ANS = [True] * n

    def add_clause(self, i, f, j, g):
        fb = (int(f) + 1) % 2
        gb = (int(g) + 1) % 2
        self.S.add_edge(2*i + fb, 2*j + g)
        self.S.add_edge(2*j + gb, 2*i + f)

    def satisfiable(self):
        n = self.n
        sl = self.S.scc_list()
        A = [-1] * (2*n)
        for i in range(len(sl)):
            for j in range(len(sl[i])):
                A[sl[i][j]] = i
        
        for i in range(n):
            if A[2*i] == A[2*i+1]:
                return False
            self.ANS[i] = A[2*i] < A[2*i+1]
        return True

    def answer(self):
        return self.ANS

T = twosat(n)
for i in range(n):
    for j in range(i+1, n):
        
        for k in range(2):
            for l in range(2):
                if abs(C[i][k] - C[j][l]) < d:
                    
                    T.add_clause(i, (k+1)%2, j, (l+1)%2)

sa = T.satisfiable()
if sa:
    print("Yes")
    ANS = T.answer()
    for i in range(n):
        print(C[i][int(ANS[i])])
else:
    print("No")

Solution (Python):
class CSR:
    def __init__(self, n: int, edges: list):
        self.start = [0] * (n + 1)
        self.elist = [0] * len(edges)
        for e in edges:
            self.start[e[0] + 1] += 1

        for i in range(1, n + 1):
            self.start[i] += self.start[i - 1]

        counter = self.start[::]  
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1


class SccGraph:
    def __init__(self, n: int = 0):
        self.__n = n
        self.__edges = []

    def __len__(self):
        return self.__n

    def add_edge(self, s: int, t: int):
        assert 0 <= s < self.__n and 0 <= t < self.__n
        self.__edges.append([s, t])

    def scc_ids(self):
        g = CSR(self.__n, self.__edges)
        now_ord = group_num = 0
        visited = []
        low = [0] * self.__n
        order = [-1] * self.__n
        ids = [0] * self.__n
        parent = [-1] * self.__n
        for root in range(self.__n):
            if order[root] == -1:
                stack = [root, root]
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        visited.append(v)
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        for i in range(g.start[v], g.start[v + 1]):
                            t = g.elist[i]
                            if order[t] == -1:
                                stack += [t, t]
                                parent[t] = v
                            else:
                                low[v] = min(low[v], order[t])

                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = self.__n
                                ids[u] = group_num
                                if u == v:
                                    break

                            group_num += 1

                        if parent[v] != -1:
                            low[parent[v]] = min(low[parent[v]], low[v])

        for i, x in enumerate(ids):
            ids[i] = group_num - 1 - x

        return group_num, ids

    def scc(self):
        """
        強連結成分のリストを返す。この時、リストはトポロジカルソートされている
        [[強連結成分のリスト], [強連結成分のリスト], ...]
        """
        group_num, ids = self.scc_ids()
        counts = [0] * group_num
        for x in ids:
            counts[x] += 1

        groups = [[] for _ in range(group_num)]
        for i, x in enumerate(ids):
            groups[x].append(i)

        return groups


class TwoSAT():
    def __init__(self, n):
        self.n = n
        self.res = [0]*self.n
        self.scc = SccGraph(2*n)

    def add_clause(self, i, f, j, g):
        
        
        self.scc.add_edge(2*i + (not f), 2*j + g)
        self.scc.add_edge(2*j + (not g), 2*i + f)

    def satisfiable(self):
        """
        条件を足す割当が存在するかどうかを判定する。割当が存在するならばtrue、そうでないならfalseを返す。
        """
        group_num, ids = self.scc.scc_ids()
        for i in range(self.n):
            if ids[2*i] == ids[2*i + 1]: return False
            self.res[i] = (ids[2*i] < ids[2*i+1])
        return True

    def result(self):
        """
        最後に呼んだ satisfiable の、クローズを満たす割当を返す。
        """
        return self.res





import sys
input = sys.stdin.buffer.readline

N, D = map(int, input().split())
XY = []
for _ in range(N):
    X, Y = map(int, input().split())
    XY.append((X, Y))
ts = TwoSAT(N)
for i in range(N-1):
    x0, y0 = XY[i]
    for j in range(i+1, N):
        x1, y1 = XY[j]
        if abs(x0 - x1) < D:
            ts.add_clause(i, 1, j, 1)
        if abs(x0 - y1) < D:
            ts.add_clause(i, 1, j, 0)
        if abs(y0 - x1) < D:
            ts.add_clause(i, 0, j, 1)
        if abs(y0 - y1) < D:
            ts.add_clause(i, 0, j, 0)

if ts.satisfiable():
    print('Yes')
    print('\n'.join(map(str, (xy[r] for r, xy in zip(ts.result(), XY)))))
else:
    print('No')

Solution (Python):
def SCC_Tarjan(g):
    n = len(g)
    order = [-1]*n 
    low = [0]*n
    ord_now = 0
    parent = [-1]*n
    gp = [0]*n
    gp_num = 0
    S = []
    q = []
    for i in range(n):
        if order[i] == -1:
            q.append(i)
            while q:
                v = q.pop()
                if v >= 0:
                    if order[v] != -1: continue
                    order[v] = low[v] = ord_now
                    ord_now += 1
                    S.append(v)
                    q.append(~v)
                    for c in g[v]:
                        if order[c] == -1: 
                            q.append(c)
                            parent[c] = v
                        else:
                            low[v] = min(low[v], order[c])
                else:
                    v = ~v
                    if parent[v] != -1:
                        low[parent[v]] = min(low[parent[v]], low[v])
                    if low[v] == order[v]:
                        while True:
                            w = S.pop()
                            order[w] = n
                            gp[w] = gp_num
                            if w==v: break
                        gp_num += 1
 
    return gp

class TwoSAT:
    def __init__(self, n):
        self._n = n
        self._answer = [False]*n
        self._g = [[] for _ in range(2*n)]

    def add_clause(self, i: int, f: bool, j: int, g: bool) -> None:
        self._g[2*i+1-f].append(2*j+g)
        self._g[2*j+1-g].append(2*i+f)

    def satisfiable(self) -> bool:
        scc_id = SCC_Tarjan(self._g)
        for i in range(self._n):
            if scc_id[2*i] == scc_id[2*i+1]:
                return False
            self._answer[i] = scc_id[2*i] < scc_id[2*i+1]
        return True

    def answer(self):
        return self._answer






import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,d = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]

g = TwoSAT(n)
for i in range(n):
    xi,yi = xy[i]
    for j in range(i+1,n):
        xj,yj = xy[j]
        if abs(xi-xj) < d:
            g.add_clause(i,0,j,0)
        if abs(xi-yj) < d:
            g.add_clause(i,0,j,1)
        if abs(yi-xj) < d:
            g.add_clause(i,1,j,0)
        if abs(yi-yj) < d:
            g.add_clause(i,1,j,1)

tf = g.satisfiable()
if tf:
    print("Yes")
    ans = g.answer()
    
    for xyi,ai in zip(xy,ans):
        print(xyi[ai])

else:
    print("No")

Solution (Python):
from collections import defaultdict


class TwoSat:
    def __init__(self, N):
        self.N = 2*N
        self.ans = None
        self.__e = []
        self.__v = list(range(self.N))

    def add_clause(self, i, f, j, g):
        self.__e.append((2*i + (0 if f else 1), 2*j + (1 if g else 0)))
        self.__e.append((2*j + (0 if g else 1), 2*i + (1 if f else 0)))

    @staticmethod
    def scc(V, E):
        g = defaultdict(list)
        rg = defaultdict(list)
        for u, v in E:
            g[u].append(v)
            rg[v].append(u)

        o = []
        done = set()
        for u in V:
            if u in done:
                continue

            s = [(u, True)]
            while s:
                u, f = s.pop()
                if f:
                    if u in done:
                        continue
                    done.add(u)
                    s.append((u, False))
                    for v in g[u]:
                        if v in done:
                            continue
                        s.append((v, True))
                else:
                    o.append(u)

        done = set()
        ans = []
        while o:
            u = o.pop()
            if u in done:
                continue

            s = [u]
            vv = [u]
            done.add(u)
            while s:
                u = s.pop()
                for v in rg[u]:
                    if v in done:
                        continue
                    vv.append(v)
                    s.append(v)
                    done.add(v)
            ans.append(vv)

        return ans

    def satisfiable(self):
        scc = TwoSat.scc(self.__v, self.__e)
        cid = [-1] * (self.N)

        for i, s in enumerate(scc):
            for v in s:
                cid[v] = i

        for i in range(self.N//2):

            if cid[2*i] == cid[2*i+1]:
                self.ans = None
                return False

        self.ans = []
        for i in range(self.N//2):
            self.ans.append(cid[2*i] < cid[2*i+1])

        return True


def atcoder_practice2_h():
    N, D = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N)]

    ts = TwoSat(N)
    for i, (x1, y1) in enumerate(XY):
        for j in range(i+1, N):
            x2, y2 = XY[j]
            if abs(x1 - x2) < D:
                ts.add_clause(i, False, j, False)

            if abs(y1 - y2) < D:
                ts.add_clause(i, True, j, True)

            if abs(x1 - y2) < D:
                ts.add_clause(i, False, j, True)

            if abs(y1 - x2) < D:
                ts.add_clause(i, True, j, False)

    if not ts.satisfiable():
        print('No')
    else:
        print('Yes')
        for i, b in enumerate(ts.ans):
            print(XY[i][0 if b else 1])


if __name__ == "__main__":
    atcoder_practice2_h()

Solution (Python):
from collections import defaultdict


class TwoSat:
    def __init__(self, V):
        self.N = len(V)
        self.ans = None
        self.__e = []
        self.__v = V

    def add_clause(self, i, f, j, g):
        self.__e.append((2*i + (0 if f else 1), 2*j + (1 if g else 0)))
        self.__e.append((2*j + (0 if g else 1), 2*i + (1 if f else 0)))

    @staticmethod
    def scc(V, E):
        g = defaultdict(list)
        rg = defaultdict(list)
        for u, v in E:
            g[u].append(v)
            rg[v].append(u)

        o = []
        done = set()
        for u in V:
            if u in done:
                continue

            s = [(u, True)]
            while s:
                u, f = s.pop()
                if f:
                    if u in done:
                        continue
                    done.add(u)
                    s.append((u, False))
                    for v in g[u]:
                        if v in done:
                            continue
                        s.append((v, True))
                else:
                    o.append(u)

        done = set()
        ans = []
        while o:
            u = o.pop()
            if u in done:
                continue

            s = [u]
            vv = [u]
            done.add(u)
            while s:
                u = s.pop()
                for v in rg[u]:
                    if v in done:
                        continue
                    vv.append(v)
                    s.append(v)
                    done.add(v)
            ans.append(vv)

        return ans

    def satisfiable(self):
        scc = TwoSat.scc(self.__v, self.__e)
        cid = [-1] * (self.N)

        for i, s in enumerate(scc):
            for v in s:
                cid[v] = i

        for i in range(self.N//2):

            if cid[2*i] == cid[2*i+1]:
                self.ans = None
                return False

        self.ans = []
        for i in range(self.N//2):
            self.ans.append(cid[2*i] < cid[2*i+1])

        return True


def atcoder_practice2_h():
    
    N, D = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N)]

    ts = TwoSat(list(range(2*N)))
    for i, (x1, y1) in enumerate(XY):
        for j in range(i+1, N):
            x2, y2 = XY[j]
            if abs(x1 - x2) < D:
                ts.add_clause(i, False, j, False)

            if abs(y1 - y2) < D:
                ts.add_clause(i, True, j, True)

            if abs(x1 - y2) < D:
                ts.add_clause(i, False, j, True)

            if abs(y1 - x2) < D:
                ts.add_clause(i, True, j, False)

    if not ts.satisfiable():
        print('No')
    else:
        print('Yes')
        for i, b in enumerate(ts.ans):
            print(XY[i][0 if b else 1])


if __name__ == "__main__":
    atcoder_practice2_h()

Solution (Python):
from collections import defaultdict

class TwoSat:
    def __init__(self, N):
        self.N = N
        self.ans = None
        self.__e = []
        self.__v = list(range(N))

    def add_clause(self, i, f, j, g):
        self.__e.append((2*i + (0 if f else 1), 2*j + (1 if g else 0)))
        self.__e.append((2*j + (0 if g else 1), 2*i + (1 if f else 0)))

    @staticmethod
    def scc(V, E):
        g = defaultdict(list)
        rg = defaultdict(list)
        for u, v in E:
            g[u].append(v)
            rg[v].append(u)

        o = []
        done = set()
        for u in V:
            if u in done:
                continue

            s = [(u, True)]
            while s:
                u, f = s.pop()
                if f:
                    if u in done:
                        continue
                    done.add(u)
                    s.append((u, False))
                    for v in g[u]:
                        if v in done:
                            continue
                        s.append((v, True))
                else:
                    o.append(u)

        done = set()
        ans = []
        while o:
            u = o.pop()
            if u in done:
                continue

            s = [u]
            vv = [u]
            done.add(u)
            while s:
                u = s.pop()
                for v in rg[u]:
                    if v in done:
                        continue
                    vv.append(v)
                    s.append(v)
                    done.add(v)
            ans.append(vv)

        return ans


    def satisfiable(self):
        scc = TwoSat.scc(self.__v, self.__e)
        cid = [-1] * (self.N)

        for i, s in enumerate(scc):
            for v in s:
                cid[v] = i

        for i in range(self.N//2):

            if cid[2*i] == cid[2*i+1]:
                self.ans = None
                return False

        self.ans = []
        for i in range(self.N//2):
            self.ans.append(cid[2*i] < cid[2*i+1])

        return True




def atcoder_practice2_h():
    N, D = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N)]


    ts = TwoSat(2*N)
    for i, (x1, y1) in enumerate(XY):
        for j in range(i+1, N):
            x2, y2 = XY[j]
            if abs(x1 - x2) < D:
                ts.add_clause(i, False, j, False)

            if abs(y1 - y2) < D:
                ts.add_clause(i, True, j, True)

            if abs(x1 - y2) < D:
                ts.add_clause(i, False, j, True)

            if abs(y1 - x2) < D:
                ts.add_clause(i, True, j, False)

    if not ts.satisfiable():
        print('No')
    else:
        print('Yes')
        for i, b in enumerate(ts.ans):
            print(XY[i][0 if b else 1])




if __name__ == "__main__":
    atcoder_practice2_h()

Solution (Python):
N,D = map(int,input().split())
XY = [tuple(map(int,input().split())) for i in range(N)]

import sys
sys.setrecursionlimit(10**8)
class Scc:
    def __init__(self,n):
        self.n = n
        self.edges = []

    def add_edge(self,fr,to):
        assert 0 <= fr < self.n
        assert 0 <= to < self.n
        self.edges.append((fr, to))

    def scc(self):
        csr_start = [0] * (self.n + 1)
        csr_elist = [0] * len(self.edges)
        for fr,to in self.edges:
            csr_start[fr + 1] += 1
        for i in range(1,self.n+1):
            csr_start[i] += csr_start[i-1]
        counter = csr_start[:]
        for fr,to in self.edges:
            csr_elist[counter[fr]] = to
            counter[fr] += 1

        self.now_ord = self.group_num = 0
        self.visited = []
        self.low = [0] * self.n
        self.ord = [-1] * self.n
        self.ids = [0] * self.n
        def _dfs(v):
            self.low[v] = self.ord[v] = self.now_ord
            self.now_ord += 1
            self.visited.append(v)
            for i in range(csr_start[v], csr_start[v+1]):
                to = csr_elist[i]
                if self.ord[to] == -1:
                    _dfs(to)
                    self.low[v] = min(self.low[v], self.low[to])
                else:
                    self.low[v] = min(self.low[v], self.ord[to])
            if self.low[v] == self.ord[v]:
                while 1:
                    u = self.visited.pop()
                    self.ord[u] = self.n
                    self.ids[u] = self.group_num
                    if u==v: break
                self.group_num += 1
        for i in range(self.n):
            if self.ord[i] == -1: _dfs(i)
        for i in range(self.n):
            self.ids[i] = self.group_num - 1 - self.ids[i]

        groups = [[] for _ in range(self.group_num)]
        for i in range(self.n):
            groups[self.ids[i]].append(i)
        return groups

class TwoSat:
    def __init__(self,n=0):
        self.n = n
        self.answer = []
        self.scc = Scc(2*n)

    def add_clause(self, i:int, f:bool, j:int, g:bool):
        assert 0 <= i < self.n
        assert 0 <= j < self.n
        self.scc.add_edge(2*i + (not f), 2*j + g)
        self.scc.add_edge(2*j + (not g), 2*i + f)

    def satisfiable(self):
        g = self.scc.scc()
        for i in range(self.n):
            if self.scc.ids[2*i] == self.scc.ids[2*i+1]: return False
            self.answer.append(self.scc.ids[2*i] < self.scc.ids[2*i+1])
        return True

    def get_answer(self):
        return self.answer

ts = TwoSat(N)
for i in range(N-1):
    xi,yi = XY[i]
    for j in range(i+1,N):
        xj,yj = XY[j]
        if abs(xi - xj) < D:
            ts.add_clause(i, False, j, False)
        if abs(xi - yj) < D:
            ts.add_clause(i, False, j, True)
        if abs(yi - xj) < D:
            ts.add_clause(i, True, j, False)
        if abs(yi - yj) < D:
            ts.add_clause(i, True, j, True)
if not ts.satisfiable():
    print('No')
    exit()
print('Yes')
ans = []
for b,(x,y) in zip(ts.get_answer(), XY):
    if b:
        ans.append(x)
    else:
        ans.append(y)
print(*ans, sep='\n')

Solution (Python):
import sys
sys.setrecursionlimit(10**7)


class SCC:
    def __init__(self,N):
        self.N = N
        self.graph = [[] for _ in range(N)]
        self.graph_rev = [[] for _ in range(N)]
        self.flag = [False]*N

    def add_edge(self,start,end):
        if start == end:
            return
        self.graph[start].append(end)
        self.graph_rev[end].append(start)

    def dfs(self,node,graph):
        self.flag[node] = True
        for n in graph[node]:
            if self.flag[n]:
                continue
            self.dfs(n,graph)
        self.order.append(node)

    def first_dfs(self):
        self.flag = [False]*self.N
        self.order = []
        for i in range(self.N):
            if self.flag[i] == False:
                self.dfs(i,self.graph)

    def second_dfs(self):
        self.flag = [False]*self.N
        self.ans = []
        for n in reversed(self.order):
            if self.flag[n]:
                continue
            self.flag[n] = True
            self.order = []
            self.dfs(n,self.graph_rev)
            self.order.reverse()
            self.ans.append(self.order)

    def scc(self):
        self.first_dfs()
        self.second_dfs()
        return self.ans


class Two_SAT():
    def __init__(self,N):
        self.N = N
        self.e = [[] for _ in range(2*N)]

    def add_condition(self,start,bool_start,end,bool_end):  
        self.e[start*2+(bool_start^1)].append(end*2+bool_end)
        self.e[end*2+(bool_end^1)].append(start*2+bool_start)

    def satisfiable(self):
        scc = SCC(2*self.N)
        for i in range(2*self.N):
            for j in self.e[i]:
                scc.add_edge(i,j)
        C = scc.scc()
        I = [0]*(2*self.N)
        for i in range(len(C)):
            for j in C[i]:
                I[j] = i
        res = [0]*(2*self.N)
        for i in range(self.N):
            if I[2*i] == I[2*i+1]:
                return (False,res)
            if I[2*i] < I[2*i+1]:
                res[i] = 1
        return (True,res)


def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,D = MI()
TS = Two_SAT(N)
XY = [tuple(MI()) for _ in range(N)]

for i in range(N-1):
    x1,y1 = XY[i]
    for j in range(i+1,N):
        x2,y2 = XY[j]
        if abs(x1-x2) < D:
            TS.add_condition(i,1,j,1)
        if abs(x1-y2) < D:
            TS.add_condition(i,1,j,0)
        if abs(y1-x2) < D:
            TS.add_condition(i,0,j,1)
        if abs(y1-y2) < D:
            TS.add_condition(i,0,j,0)



bl,sa = TS.satisfiable()

if not bl:
    print('No')
else:
    print('Yes')
    print(*[XY[i][sa[i]] for i in range(N)],sep='\n')

Solution (Python):
class csr:
    def __init__(self, n: int, edges: list):
        self.start = [0] * (n + 1)
        self.elist = [0] * len(edges)
        for e in edges:
            self.start[e[0] + 1] += 1
        for i in range(1, n + 1):
            self.start[i] += self.start[i - 1]
        counter = self.start[::]
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1


class internal_scc_graph:
    def __init__(self, n: int = 0):
        self.__n = n
        self.__edges = []

    def num_vertices(self):
        return self.__n

    def add_edge(self, from_: int, to: int):
        self.__edges.append([from_, to])

    def scc_ids(self):
        g = csr(self.__n, self.__edges)
        now_ord = 0
        group_num = 0
        visited = []
        low = [0] * self.__n
        ord = [-1] * self.__n
        ids = [0] * self.__n
        parent = [-1] * self.__n

        for root in range(self.__n):
            if(ord[root] == -1):
                stack = []
                stack.extend([root] * 2)
                while(stack):
                    v = stack.pop()
                    if(ord[v] == -1):
                        visited.append(v)
                        low[v] = now_ord
                        ord[v] = now_ord
                        now_ord += 1
                        for i in range(g.start[v], g.start[v + 1]):
                            to = g.elist[i]
                            if(ord[to] == -1):
                                stack.extend([to] * 2)
                                parent[to] = v
                            else:
                                low[v] = min(low[v], ord[to])
                    else:
                        if(low[v] == ord[v]):
                            while(True):
                                u = visited.pop()
                                ord[u] = self.__n
                                ids[u] = group_num
                                if(u == v):
                                    break
                            group_num += 1
                        if(parent[v] != -1):
                            low[parent[v]] = min(low[parent[v]], low[v])

        for i, x in enumerate(ids):
            ids[i] = group_num - 1 - x
        return [group_num, ids]


class two_sat:
    def __init__(self, n: int = 0):
        self.__n = n
        self.__answer = [0] * n
        self.__scc = internal_scc_graph(2 * n)

    def add_clause(self, i: int, f: bool, j: int, g: bool):
        assert (0 <= i) & (i < self.__n)
        assert (0 <= j) & (j < self.__n)
        self.__scc.add_edge(2 * i + (1 - f), 2 * j + g)
        self.__scc.add_edge(2 * j + (1 - g), 2 * i + f)

    def satisfiable(self):
        id = self.__scc.scc_ids()[1]
        for i in range(self.__n):
            if(id[2 * i] == id[2 * i + 1]):
                return False
            self.__answer[i] = (id[2 * i] < id[2 * i + 1])
        return True

    def answer(self):
        return self.__answer

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,d = map(int,readline().split())
xy = [list(map(int, i.split())) for i in readlines()]

ts = two_sat(n)
for i in range(n-1):
    for j in range(i+1,n):
        for ii,jj in zip([0,0,1,1],[0,1,0,1]):
            if(abs(xy[i][ii] - xy[j][jj]) < d):
                ts.add_clause(i, 1-ii, j, 1-jj)

if(ts.satisfiable()):
    print('Yes')
else:
    print('No')
    exit()

ans = []
for i,tf in enumerate(ts.answer()):
    ans.append(xy[i][tf])
print('\n'.join(map(str,ans)))

Solution (Python):
code = """






from libcpp.vector cimport vector
from libcpp cimport bool
from libc.stdio cimport getchar, printf
from libcpp.string cimport string
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l, int n):
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l, int n):
    for i in range(n): printf("%ld ", l[i])
cdef extern from "<atcoder/twosat>" namespace "atcoder":
    cdef cppclass two_sat:
        two_sat(int n)
        void add_clause(int i, bool f, int j, bool g)
        bool satisfiable()
        vector[bool] answer()

cdef class TwoSat:
    cdef two_sat *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new two_sat(n)
    cpdef void add_clause(self, int i, bool f, int j, bool g):
        self._thisptr.add_clause(i, f, j, g)
    cpdef bool satisfiable(self):
        return self._thisptr.satisfiable()
    cpdef vector[bool] answer(self):
        return self._thisptr.answer()
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import ReadInt, TwoSat

def main():
  N,D=ReadInt(2)
  xy = [ReadInt(2) for _ in range(N)]
  ts=TwoSat(N)
  for i in range(N-1):
    for j in range(i+1,N):
      for k1,k2 in [(0,0),(0,1),(1,0),(1,1)]:
        pos1,pos2 = xy[i][k1],xy[j][k2]
        if abs(pos2-pos1)<D:
          ts.add_clause(i,k1^1,j,k2^1)

  if ts.satisfiable():
    print('Yes')
    ans = ts.answer()
    print(*[xy[i][ans[i]] for i in range(N)],sep="\n")
  else:
    print('No')

if __name__=="__main__":
  main()