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:
def SCC_Tarjan(g):
    n = len(g)
    order = [-1]*n # 負なら未処理、[0,n) ならpre-order, n ならvisited
    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

###########################################################################                        
###########################################################################                        

# coding: utf-8
# Your code here!
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()
    #print(ans)
    for xyi,ai in zip(xy,ans):
        print(xyi[ai])

else:
    print("No")

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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():
    # https://atcoder.jp/contests/practice2/submissions/16823214
    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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
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):  # start or 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)

# 0:X,1:Y

bl,sa = TS.satisfiable()

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

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

# Strongly connected component
# derived from https://atcoder.jp/contests/practice2/submissions/16645774


def get_strongly_connected_components(edges, num_vertex):
    """
    edges: {v: [v]}
    """
    from collections import defaultdict

    reverse_edges = defaultdict(list)
    for v1 in edges:
        for v2 in edges[v1]:
            reverse_edges[v2].append(v1)

    terminate_order = []
    done = [0] * num_vertex  # 0 -> 1 -> 2
    count = 0
    for i0 in range(num_vertex):
        if done[i0]:
            continue
        queue = [~i0, i0]
        # dfs
        while queue:
            i = queue.pop()
            if i < 0:
                if done[~i] == 2:
                    continue
                done[~i] = 2
                terminate_order.append(~i)
                count += 1
                continue
            if i >= 0:
                if done[i]:
                    continue
                done[i] = 1
            for j in edges[i]:
                if done[j]:
                    continue
                queue.append(~j)
                queue.append(j)

    done = [0] * num_vertex
    result = []
    for i0 in terminate_order[::-1]:
        if done[i0]:
            continue
        component = []
        queue = [~i0, i0]
        while queue:
            i = queue.pop()
            if i < 0:
                if done[~i] == 2:
                    continue
                done[~i] = 2
                component.append(~i)
                continue
            if i >= 0:
                if done[i]:
                    continue
                done[i] = 1
            for j in reverse_edges[i]:
                if done[j]:
                    continue
                queue.append(~j)
                queue.append(j)
        result.append(component)
    return result


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, D, data):
    # edges = [[] for i in range(N * 2)]
    # edges = []
    from collections import defaultdict
    edges = defaultdict(list)

    def add_then_edge(i, bool_i, j, bool_j):
        edges[i * 2 + int(bool_i)].append(j * 2 + int(bool_j))
        # edges.append((i * 2 + int(bool_i), j * 2 + int(bool_j)))

    for i in range(N):
        xi, yi = data[i]
        for j in range(i + 1, N):
            xj, yj = data[j]
            if abs(xi - xj) < D:
                add_then_edge(i, 0, j, 1)
                add_then_edge(j, 0, i, 1)
            if abs(xi - yj) < D:
                add_then_edge(i, 0, j, 0)
                add_then_edge(j, 1, i, 1)
            if abs(yi - xj) < D:
                add_then_edge(i, 1, j, 1)
                add_then_edge(j, 0, i, 0)
            if abs(yi - yj) < D:
                add_then_edge(i, 1, j, 0)
                add_then_edge(j, 1, i, 0)

    scc = get_strongly_connected_components(edges, N * 2)
    group_id = [0] * (2 * N)
    for i, xs in enumerate(scc):
        for x in xs:
            group_id[x] = i

    ret = [0] * N
    for i in range(N):
        if group_id[2 * i] == group_id[2 * i + 1]:
            print("No")
            return

        ret[i] = (group_id[2 * i] < group_id[2 * i + 1])

    print("Yes")
    for i in range(N):
        print(data[i][ret[i]])


def main():
    # parse input
    N, D = map(int, input().split())
    data = []
    for _i in range(N):
        data.append(tuple(map(int, input().split())))

    solve(N, D, data)


# tests
T1 = """
3 2
1 4
2 5
0 6
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
Yes
4
2
6
"""

T2 = """
3 3
1 4
2 5
0 6
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
No
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()