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
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7





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  
    count = 0
    for i0 in range(num_vertex):
        if done[i0]:
            continue
        queue = [~i0, i0]
        
        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):
    
    
    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))
        

    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():
    
    N, D = map(int, input().split())
    data = []
    for _i in range(N):
        data.append(tuple(map(int, input().split())))

    solve(N, D, data)



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

Solution (Python):
code = r"""




from libcpp cimport bool
from libcpp.string cimport string
from libcpp.vector cimport vector

cdef extern from "<atcoder/dsu>" namespace "atcoder":
    cpdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
cdef class dsu_:
    cdef dsu *ptr
    def __cinit__(self, int n): self.ptr = new dsu(n)
    def __dealloc__(self): del self.ptr
    cpdef int merge(self,a,b): return self.ptr.merge(a,b)
    cpdef bool same(self,a,b): return self.ptr.same(a,b)
    cpdef int leader(self,a): return self.ptr.leader(a)
    cpdef int size(self,a): return self.ptr.size(a)
    cpdef vector[vector[int]] groups(self): return self.ptr.groups()

cdef extern from "<atcoder/fenwicktree>" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)
cdef class fenwick_tree_:
    cdef fenwick_tree[int] *ptr
    def __cinit__(self, int n): self.ptr = new fenwick_tree[int](n)  
    def __dealloc__(self): del self.ptr
    cpdef void add(self, int p, long x): self.ptr.add(p, x)
    cpdef long sum(self, int l, int r): return self.ptr.sum(l, r)

cdef extern from "<atcoder/string>" namespace "atcoder":
    vector[int] suffix_array(vector[int] s, int upper)
    vector[int] suffix_array(vector[long] s)
    vector[int] suffix_array(string s)
    vector[int] lcp_array(vector[long] s, vector[int] sa)
    vector[int] lcp_array(string s, vector[int] sa)
    vector[int] z_algorithm(vector[long] s)
    vector[int] z_algorithm(string s)
cpdef vector[int] suffix_array_u(vector[int] s, int upper): return suffix_array(s, upper)
cpdef vector[int] suffix_array_l(vector[long] s): return suffix_array(s)
cpdef vector[int] suffix_array_s(string s): return suffix_array(s)
cpdef vector[int] lcp_array_l(vector[long] s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] lcp_array_s(string s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] z_algorithm_l(vector[long] s): return z_algorithm(s)
cpdef vector[int] z_algorithm_s(string s): return z_algorithm(s)

cdef extern from "<atcoder/maxflow>" namespace "atcoder":
    cdef cppclass mf_graph[Cap]:
        mf_graph(int n)
        int add_edge(int frm, int to, Cap cap)
        Cap flow(int s, int t)
        Cap flow(int s, int t, Cap flow_limit)
        vector[bool] min_cut(int s)
        cppclass edge:
            int frm "from", to
            Cap cap, flow
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()
        void change_edge(int i, Cap new_cap, Cap new_flow)
cdef class mf_graph_:
    cdef mf_graph[int] *ptr
    def __cinit__(self, int n): self.ptr = new mf_graph[int](n)  
    def __dealloc__(self): del self.ptr
    cpdef int add_edge(self, int frm, int to, int cap): return self.ptr.add_edge(frm, to, cap)
    cpdef int flow(self, int s, int t): return self.ptr.flow(s, t)
    cpdef int flow_limit(self, int s, int t, int flow_limit): return self.ptr.flow(s, t, flow_limit)
    cpdef vector[bool] min_cut(self, int s): return self.ptr.min_cut(s)
    cpdef vector[int] get_edge(self, int i):
        cdef mf_graph[int].edge *e = new mf_graph[int].edge(self.ptr.get_edge(i))
        cdef vector[int] *ret_e = new vector[int]()        
        ret_e.push_back(e.frm)
        ret_e.push_back(e.to)
        ret_e.push_back(e.cap)
        ret_e.push_back(e.flow)
        return ret_e[0]
    cpdef vector[vector[int]] edges(self):
        cdef vector[mf_graph[int].edge] es = self.ptr.edges()
        cdef vector[vector[int]] *ret_es = new vector[vector[int]](es.size())
        for i in range(es.size()):
            ret_es.at(i).push_back(es.at(i).frm)
            ret_es.at(i).push_back(es.at(i).to)
            ret_es.at(i).push_back(es.at(i).cap)
            ret_es.at(i).push_back(es.at(i).flow)
        return ret_es[0]
    cpdef void change_edge(self, int i, int new_cap, int new_flow): self.ptr.change_edge(i, new_cap, new_flow)

cdef extern from *:
    ctypedef int MOD "998244353"
    ctypedef long long ll "long long"
cdef extern from "<atcoder/convolution>" namespace "atcoder":
    vector[int] convolution[m](vector[int] a, vector[int] b)
    vector[ll] convolution_ll(vector[ll] a, vector[ll] b)
cpdef vector[int] convolution_(vector[int] a, vector[int] b): return convolution[MOD](a, b)
cpdef vector[ll] convolution_ll_(vector[ll] a, vector[ll] b): return convolution_ll(a, b)

cdef extern from "<atcoder/scc>" namespace "atcoder":
    cdef cppclass scc_graph:
        scc_graph(int n)
        void add_edge(int fr, int to)
        vector[vector[int]] scc()
cdef class scc_graph_:
    cdef scc_graph *ptr
    def __cinit__(self, int n): self.ptr = new scc_graph(n)  
    def __dealloc__(self): del self.ptr
    cpdef void add_edge(self, int fr, int to): self.ptr.add_edge(fr, to)
    cpdef vector[vector[int]] scc(self): return self.ptr.scc()

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 two_sat_:
    cdef two_sat *ptr
    def __cinit__(self, int n): self.ptr = new two_sat(n)
    def __dealloc__(self): del self.ptr
    cpdef void add_clause(self, int i, bool f, int j, bool g): self.ptr.add_clause(i, f, j, g)
    cpdef bool satisfiable(self): return self.ptr.satisfiable()
    cpdef vector[bool] answer(self): return self.ptr.answer()
"""

import os
try:
    from atcoder import *
except:
    open('atcoder.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')

N,D=map(int,input().split())
X,Y=zip(*[list(map(int,input().split())) for i in range(N)])
ts=two_sat_(N)
for i in range(N):
    for j in range(i+1,N):
        if abs(X[i]-X[j])<D:
            ts.add_clause(i,False,j,False)
        if abs(X[i]-Y[j])<D:
            ts.add_clause(i,False,j,True)
        if abs(Y[i]-X[j])<D:
            ts.add_clause(i,True,j,False)
        if abs(Y[i]-Y[j])<D:
            ts.add_clause(i,True,j,True)
if ts.satisfiable():
    print('Yes')
    print(*[X[i] if e else Y[i] for i,e in enumerate(ts.answer())],sep='\n')
else:
    print('No')

Solution (Python):
class DiGraph:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]

    def add_edge(self, fr, to):
        self.graph[fr].append(to)
        self.rev[to].append(fr)
        self.deg[to] += 1

    def scc_ids(self):
        group = [None for _ in range(self.n)]
        used = [0 for _ in range(self.n)]
        order = []
        for s in range(self.n):
            if not used[s]:
                stack = [s]
                used[s] = 1
                while stack:
                    node = stack.pop()
                    movable = False
                    for adj in self.graph[node]:
                        if not used[adj]:
                            movable = True
                            used[adj] = 1
                            stack.append(node)
                            stack.append(adj)
                            break
                    if not movable:
                        order.append(node)
        used = [0 for _ in range(self.n)]
        count = 0
        for s in order[::-1]:
            if not used[s]:
                stack = [s]
                group[s] = count
                while stack:
                    node = stack.pop()
                    used[node] = 1
                    for adj in self.rev[node]:
                        if not used[adj]:
                            group[adj] = count
                            stack.append(adj)
                count += 1
        return group, count


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

    def add_clause(self, i: int, f: bool, j: int, g: bool):  
        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):
        group, cnt = self.scc.scc_ids()
        for i in range(self.n):
            if group[2 * i] == group[2 * i + 1]:
                return False
            self.res[i] = (group[2 * i] > group[2 * i + 1])
        return True

    def result(self):
        return self.res


N, D = map(int, input().split())
XY = [tuple(map(int, input().split())) for _ in range(N)]

ts = TwoSAT(N)

for i in range(N-1):
    x1, y1 = XY[i][0], XY[i][1]
    for j in range(i+1, N):
        x2, y2 = XY[j][0], XY[j][1]

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

if ts.satisfiable():
    print('Yes')
    res = ts.result()
    for i in range(N):
        print(XY[i][0 if res[i] else 1])
else:
    print('No')

Solution (Python):



class two_sat:
  def __init__(s):
    s._n = 0
    s.scc = scc_graph(0)
  def __init__(s, n):
    s._n = n
    s._answer = [False] * n
    s.scc = scc_graph(2 * n)

  
  
  def add_clause(s, i, f, j, g):
    s.scc.add_edge(2 * i + (not f), 2 * j + (g))
    s.scc.add_edge(2 * j + (not g), 2 * i + (f))
  
  
  
  def satisfiable(s):
    id = s.scc.scc_ids()[1]
    for i in range(s._n):
      if id[2 * i] == id[2 * i + 1]: return False
      s._answer[i] = id[2 * i] < id[2 * i + 1]
    return True

  
  
  
  def answer(s): return s._answer






import sys
sys.setrecursionlimit(1000000)

class scc_graph:
  
  def __init__(s, n): 
    s._n = n
    s.g = {}
  def num_vertices(s): return s._n
  
  
  def add_edge(s, frm, to): 
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]

  
  def scc_ids(s):
    now_ord = group_num = 0
    visited = []
    low = [0] * s._n
    ord = [-1] * s._n
    ids = [0] * s._n
    
    def dfs(self, v, now_ord, group_num):
      low[v] = ord[v] = now_ord
      now_ord += 1
      visited.append(v)
      if v in s.g:
        for to in s.g[v]:
          if ord[to] == -1:
            now_ord, group_num = self(self, to, now_ord, group_num)
            low[v] = min(low[v], low[to])
          else:
            low[v] = min(low[v], ord[to])
      if low[v] == ord[v]:
        while True:
          u = visited.pop()
          ord[u] = s._n
          ids[u] = group_num
          if u == v: break
        group_num += 1
      return now_ord, group_num

    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = dfs(dfs, i, now_ord, group_num)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    return group_num, ids

  
  
  def scc(s):
    group_num, ids = s.scc_ids()
    counts = [0] * group_num
    for x in ids: counts[x] += 1
    groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[i]].append(i)
    return groups

  class edge:
    def __init__(s, frm, to):
      s.frm = frm
      s.to = to



def main():
  input = sys.stdin.readline

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

  ts = two_sat(N)

  for i in range(N):
    for j in range(i + 1, N):
      xi, yi = XY[i]
      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")
  answer = ts.answer()
  for i in range(N):
    x, y = XY[i]
    if answer[i]:
      print(x)
    else:
      print(y)

main()

Solution (Python):



class two_sat:
  def __init__(s):
    s._n = 0
    s.scc = scc_graph(0)
  def __init__(s, n):
    s._n = n
    s._answer = [False] * n
    s.scc = scc_graph(2 * n)

  
  
  def add_clause(s, i, f, j, g):
    s.scc.add_edge(2 * i + (not f), 2 * j + (g))
    s.scc.add_edge(2 * j + (not g), 2 * i + (f))
  
  
  
  def satisfiable(s):
    id = s.scc.scc_ids()[1]
    for i in range(s._n):
      if id[2 * i] == id[2 * i + 1]: return False
      s._answer[i] = id[2 * i] < id[2 * i + 1]
    return True

  
  
  
  def answer(s): return s._answer






import sys
sys.setrecursionlimit(1000000)

class scc_graph:
  
  def __init__(s, n): 
    s._n = n
    s.g = {}
  def num_vertices(s): return s._n
  
  
  def add_edge(s, frm, to): 
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]

  
  def scc_ids(s):
    now_ord = group_num = 0
    visited = []
    low = [0] * s._n
    ord = [-1] * s._n
    ids = [0] * s._n
    
    def dfs(self, v, now_ord, group_num):
      low[v] = ord[v] = now_ord
      now_ord += 1
      visited.append(v)
      if v in s.g:
        for to in s.g[v]:
          if ord[to] == -1:
            now_ord, group_num = self(self, to, now_ord, group_num)
            low[v] = min(low[v], low[to])
          else:
            low[v] = min(low[v], ord[to])
      if low[v] == ord[v]:
        while True:
          u = visited.pop()
          ord[u] = s._n
          ids[u] = group_num
          if u == v: break
        group_num += 1
      return now_ord, group_num

    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = dfs(dfs, i, now_ord, group_num)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    return group_num, ids

  
  
  def scc(s):
    group_num, ids = s.scc_ids()
    counts = [0] * group_num
    for x in ids: counts[x] += 1
    groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[i]].append(i)
    return groups

  class edge:
    def __init__(s, frm, to):
      s.frm = frm
      s.to = to



def main():
  input = sys.stdin.readline

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

  ts = two_sat(N)

  for i in range(N):
    for j in range(i + 1, N):
      xi, yi = XY[i]
      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")
  answer = ts.answer()
  for i in range(N):
    x, y = XY[i]
    if answer[i]:
      print(x)
    else:
      print(y)

main()

Solution (Python):
class StronglyConnectedComponents():
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]

    def add_edge(self, fr, to):
        self.graph[fr].append(to)
        self.rev[to].append(fr)

    def scc_id(self):
        group = [0] * self.n
        order = []
        for s in range(self.n):
            if group[s]: continue
            stack = [s]
            group[s] = -1
            while stack:
                node = stack.pop()
                for adj in self.graph[node]:
                    if group[adj]: continue
                    group[adj] = -1
                    stack.append(node)
                    stack.append(adj)
                    break
                else:
                    order.append(node)
        cnt = 0
        for s in order[::-1]:
            if group[s] != -1: continue
            stack = [s]
            group[s] = cnt
            while stack:
                node = stack.pop()
                for adj in self.rev[node]:
                    if group[adj] != -1: continue
                    group[adj] = cnt
                    stack.append(adj)
            cnt += 1
        return group, cnt

    def scc(self):
        group, cnt = self.scc_id()
        res = [[] for _ in range(cnt)]
        for i in range(self.n):
            res[group[i]].append(i)
        return res

class TwoSAT():
    def __init__(self, n):
        self.n = n
        self.res = [0] * self.n
        self.scc = StronglyConnectedComponents(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):
        group, cnt = self.scc.scc_id()
        for i in range(self.n):
            if group[2 * i] == group[2 * i + 1]: return False
            self.res[i] = (group[2 * i] < group[2 * i + 1])
        return True

    def result(self):
        return self.res

import sys
input = sys.stdin.buffer.readline

N, D = map(int, input().split())
F = [tuple(map(int, input().split())) for _ in range(N)]

ts = TwoSAT(N)

for i in range(N - 1):
    x0, y0 = F[i]
    for j in range(i + 1, N):
        x1, y1 = F[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, (f[r] for r, f in zip(ts.result(), F)))))
else:
    print('No')

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

sys.setrecursionlimit(10**7)

class SCC():
	def __init__(self, n):
		self.n = n
		self.adj = [[] for _ in range(self.n)]
		self.inv = [[] for _ in range(self.n)]
		self.post_order = []
		self.visited = [False for _ in range(self.n)]
		self.dag_v_to_num = [-1 for _ in range(self.n)]
		self.dag_num_to_v = []
		return

	def add_edge(self, u, v):
		self.adj[u].append(v)
		self.inv[v].append(u)
		return

	def dfs1(self, i):
		for j in self.adj[i]:
			if not self.visited[j]:
				self.visited[j] = True
				self.dfs1(j)
		self.post_order.append(i)
		return

	def dfs2(self, i, num):
		self.dag_num_to_v[-1].append(i)
		self.dag_v_to_num[i] = num
		for j in self.inv[i]:
			if not self.visited[j]:
				self.visited[j] = True
				self.dfs2(j, num)
		return

	def make_scc(self):
		for i in range(self.n):
			if not self.visited[i]:
				self.visited[i] = True
				self.dfs1(i)

		self.visited = [False for _ in range(self.n)]
		num = 0
		for i in range(self.n-1, -1, -1):
			if not self.visited[self.post_order[i]]:
				self.visited[self.post_order[i]] = True
				self.dag_num_to_v.append(list())
				self.dfs2(self.post_order[i], num)
				num += 1

		return self.dag_v_to_num, self.dag_num_to_v


class TwoSAT(SCC):
	"""
	node 2*i  : x_i
	node 2*i+1: not x_i
	"""
	def __init__(self, n):
		super().__init__(2*n)
		return

	def add_clause(self, i, f, j, g):
		super().add_edge(2*i + (1^f), 2*j + g)
		super().add_edge(2*j + (1^g), 2*i + f)
		return

	def satisfy(self):
		topol, _ = super().make_scc()
		res = []
		for i in range(0, self.n, 2):
			x, y = topol[i], topol[i+1]
			if x == y:
				return False, None
			elif x > y:
				res.append(False)
			else:
				res.append(True)
		return True, res

n, d = map(int, input().split())
ts = TwoSAT(n)
flags = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
	for j in range(i+1, n):
		for k in range(4):
			f, g = k//2, k%2
			if abs(flags[i][f] - flags[j][g]) < d:
				ts.add_clause(i, f, j, g)

ok, ans = ts.satisfy()
if not ok:
	print("No")
else:
	print("Yes")
	print(*[f[1^b] for f, b in zip(flags, ans)], sep="\n")

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

sys.setrecursionlimit(10**7)

class SCC():
	def __init__(self, n):
		self.n = n
		self.adj = [[] for _ in range(self.n)]
		self.inv = [[] for _ in range(self.n)]
		self.post_order = []
		self.visited = [False for _ in range(self.n)]
		self.dag_v_to_num = [-1 for _ in range(self.n)]
		self.dag_num_to_v = []
		return

	def add_edge(self, u, v):
		self.adj[u].append(v)
		self.inv[v].append(u)
		return

	def dfs1(self, i):
		for j in self.adj[i]:
			if not self.visited[j]:
				self.visited[j] = True
				self.dfs1(j)
		self.post_order.append(i)
		return

	def dfs2(self, i, num):
		self.dag_num_to_v[-1].append(i)
		self.dag_v_to_num[i] = num
		for j in self.inv[i]:
			if not self.visited[j]:
				self.visited[j] = True
				self.dfs2(j, num)
		return

	def make_scc(self):
		for i in range(self.n):
			if not self.visited[i]:
				self.visited[i] = True
				self.dfs1(i)

		self.visited = [False for _ in range(self.n)]
		num = 0
		for i in range(self.n-1, -1, -1):
			if not self.visited[self.post_order[i]]:
				self.visited[self.post_order[i]] = True
				self.dag_num_to_v.append(list())
				self.dfs2(self.post_order[i], num)
				num += 1

		return self.dag_v_to_num, self.dag_num_to_v


class TwoSAT(SCC):
	"""
	node 2*i  : x_i
	node 2*i+1: not x_i
	"""
	def __init__(self, n):
		super().__init__(2*n)
		return

	def add_clause(self, i, f, j, g):
		super().add_edge(2*i + (1^f), 2*j + g)
		super().add_edge(2*j + (1^g), 2*i + f)
		return

	def satisfy(self):
		topol, _ = super().make_scc()
		res = []
		for i in range(0, self.n, 2):
			x, y = topol[i], topol[i+1]
			if x == y:
				return False, None
			elif x > y:
				res.append(False)
			else:
				res.append(True)
		return True, res

n, d = map(int, input().split())
ts = TwoSAT(n)
flags = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
	for j in range(i+1, n):
		for k in range(4):
			f, g = k//2, k%2
			if abs(flags[i][f] - flags[j][g]) < d:
				ts.add_clause(i, f, j, g)

ok, ans = ts.satisfy()
if not ok:
	print("No")
else:
	print("Yes")
	print(*[f[1^b] for f, b in zip(flags, ans)], sep="\n")

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

sys.setrecursionlimit(10**7)

class SCC():
	def __init__(self, n):
		self.n = n
		self.adj = [[] for _ in range(self.n)]
		self.inv = [[] for _ in range(self.n)]
		self.post_order = []
		self.visited = [False for _ in range(self.n)]
		self.dag_v_to_num = [-1 for _ in range(self.n)]
		self.dag_num_to_v = []
		return

	def add_edge(self, u, v):
		self.adj[u].append(v)
		self.inv[v].append(u)
		return

	def dfs1(self, i):
		for j in self.adj[i]:
			if not self.visited[j]:
				self.visited[j] = True
				self.dfs1(j)
		self.post_order.append(i)
		return

	def dfs2(self, i, num):
		self.dag_num_to_v[-1].append(i)
		self.dag_v_to_num[i] = num
		for j in self.inv[i]:
			if not self.visited[j]:
				self.visited[j] = True
				self.dfs2(j, num)
		return

	def make_scc(self):
		for i in range(self.n):
			if not self.visited[i]:
				self.visited[i] = True
				self.dfs1(i)

		self.visited = [False for _ in range(self.n)]
		num = 0
		for i in range(self.n-1, -1, -1):
			if not self.visited[self.post_order[i]]:
				self.visited[self.post_order[i]] = True
				self.dag_num_to_v.append(list())
				self.dfs2(self.post_order[i], num)
				num += 1

		return self.dag_v_to_num, self.dag_num_to_v


class TwoSAT(SCC):
	"""
	node 2*i  : x_i
	node 2*i+1: not x_i
	"""
	def __init__(self, n):
		super().__init__(2*n)
		return

	def add_clause(self, i, f, j, g):
		super().add_edge(2*i + (1^f), 2*j + g)
		super().add_edge(2*j + (1^g), 2*i + f)
		return

	def satisfy(self):
		topol, _ = super().make_scc()
		res = []
		for i in range(0, self.n, 2):
			x, y = topol[i], topol[i+1]
			if x == y:
				return False, None
			elif x > y:
				res.append(False)
			else:
				res.append(True)
		return True, res

n, d = map(int, input().split())
ts = TwoSAT(n)
flags = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
	for j in range(i+1, n):
		for k in range(4):
			f, g = k//2, k%2
			if abs(flags[i][f] - flags[j][g]) < d:
				ts.add_clause(i, f, j, g)

ok, ans = ts.satisfy()
if not ok:
	print("No")
else:
	print("Yes")
	for f, b in zip(flags, ans):
		print(f[1^b])

Solution (Python):
def scc(E):
    n = len(E)
    iE = [[] for _ in range(n)]
    for i, e in enumerate(E):
        for v in e:
            iE[v].append(i)
    T = []
    done = [0] * n 
    ct = 0
    for i0 in range(n):
        if done[i0]: continue
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                T.append(~i)
                ct += 1
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in E[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
    
    done = [0] * n
    SCC = []
    
    I = [0] * n
    
    for i0 in T[::-1]:
        if done[i0]: continue
        L = []
        Q = [~i0, i0]
        while Q:
            i = Q.pop()
            if i < 0:
                if done[~i] == 2: continue
                done[~i] = 2
                L.append(~i)
                
                I[~i] = len(SCC)
                
                continue
            if i >= 0:
                if done[i]: continue
                done[i] = 1
            for j in iE[i]:
                if done[j]: continue
                Q.append(~j)
                Q.append(j)
        SCC.append(L)
    return SCC, I

    
    nE = [set() for _ in range(len(SCC))]
    for i, e in enumerate(E):
        for j in e:
            if I[i] == I[j]: continue
            
            nE[I[i]].add(I[j])
    nE = [list(e) for e in nE]
    return SCC, I, nE

class twosat():
    def __init__(self, n):
        self.n = n
        self.E = [[] for _ in range(n * 2)]
    def add_clause(self, i, f, j, g):
        assert 0 <= i < self.n
        assert f == 0 or f == 1
        assert 0 <= j < self.n
        assert g == 0 or g == 1
        self.E[i * 2 + (f ^ 1)].append(j * 2 + g)
        self.E[j * 2 + (g ^ 1)].append(i * 2 + f)
    
    def satisfiable(self):
        SCC, I = scc(self.E)
        re = [0] * self.n
        for i in range(self.n):
            if I[2*i] == I[2*i+1]: return (0, [])
            if I[2*i] < I[2*i+1]: re[i] = 1
        return (1, re)

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

for i, (x1, y1) in enumerate(X):
    for j, (x2, y2) in enumerate(X[:i]):
        if abs(x1 - x2) < D:
            ts.add_clause(i, 1, j, 1)
        if abs(x1 - y2) < D:
            ts.add_clause(i, 1, j, 0)
        if abs(y1 - x2) < D:
            ts.add_clause(i, 0, j, 1)
        if abs(y1 - y2) < D:
            ts.add_clause(i, 0, j, 0)

a, sa = ts.satisfiable()
if a == 0:
    print("No")
else:
    print("Yes")
    print(*[x[r] for x, r in zip(X, sa)], sep = "\n")