AtCoder Library Practice Contest - Two SAT

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.

Examples

Input

3 2
1 4
2 5
0 6


Output

Yes
4
2
0


Input

3 3
1 4
2 5
0 6


Output

No

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
class Two_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):
		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):
		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):
		return v in self.variable

	def clause_exist(self, X, F, Y, G):
		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):
		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)))


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 copy
import sys
sys.setrecursionlimit(1000000)

class csr:

	def __init__(s, n, edges):
		s.start = [0] * (n + 1)
		s.elist = [[] for _ in range(len(edges))]
		for e in edges:
			s.start[e[0] + 1] += 1
		for i in range(1, n + 1):
			s.start[i] += s.start[i - 1]
		counter = copy.deepcopy(s.start)
		for e in edges:
			s.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class scc_graph:
	edges = []

	def __init__(s, n):
		s._n = n

	def num_vertices(s):
		return s._n

	def add_edge(s, frm, to):
		s.edges.append([frm, [to]])

	def scc_ids(s):
		g = csr(s._n, s.edges)
		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)
			for i in range(g.start[v], g.start[v + 1]):
				to = g.elist[i][0]
				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):
		ids = s.scc_ids()
		group_num = ids[0]
		counts = [0] * group_num
		for x in ids[1]:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for i in range(s._n):
			groups[ids[1][i]].append(i)
		return groups

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


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


import sys

class SCC:

	def __init__(self, N):
		self.N = N
		self.G1 = [[] for _ in range(N)]
		self.G2 = [[] for _ in range(N)]

	def add_edge(self, a, b):
		self.G1[a].append(b)
		self.G2[b].append(a)

	def scc(self):
		self.seen = [0] * self.N
		self.postorder = [-1] * self.N
		self.order = 0
		for i in range(self.N):
			if self.seen[i]:
				continue
			self._dfs(i)
		self.seen = [0] * self.N
		scclist = []
		for i in self._argsort(self.postorder, reverse=True):
			if self.seen[i]:
				continue
			cc = self._dfs2(i)
			scclist.append(cc)
		return scclist

	def _argsort(self, arr, reverse=False):
		shift = self.N.bit_length() + 2
		tmp = sorted([arr[i] << shift | i for i in range(len(arr))], reverse=reverse)
		mask = (1 << shift) - 1
		return [tmp[i] & mask for i in range(len(arr))]

	def _dfs(self, v0):
		todo = [~v0, v0]
		while todo:
			v = todo.pop()
			if v >= 0:
				self.seen[v] = 1
				for next_v in self.G1[v]:
					if self.seen[next_v]:
						continue
					todo.append(~next_v)
					todo.append(next_v)
			elif self.postorder[~v] == -1:
				self.postorder[~v] = self.order
				self.order += 1
		return

	def _dfs2(self, v):
		todo = [v]
		self.seen[v] = 1
		cc = [v]
		while todo:
			v = todo.pop()
			for next_v in self.G2[v]:
				if self.seen[next_v]:
					continue
				self.seen[next_v] = 1
				todo.append(next_v)
				cc.append(next_v)
		return cc

class TwoSAT:

	def __init__(self, N):
		self.N = N
		self.scc = SCC(2 * N)
		self.flag = -1

	def add_clause(self, i, f, j, g):
		self.scc.add_edge(f * self.N + i, (1 ^ g) * self.N + j)
		self.scc.add_edge(g * self.N + j, (1 ^ f) * self.N + i)

	def satisfiable(self):
		if self.flag == -1:
			self.scclist = self.scc.scc()
			self.order = {j: i for (i, scc) in enumerate(self.scclist) for j in scc}
			self.flag = True
			self.ans = [0] * self.N
			for i in range(self.N):
				if self.order[i] > self.order[self.N + i]:
					self.ans[i] = 1
					continue
				elif self.order[i] == self.order[i + self.N]:
					self.flag = False
					return self.flag
			return self.flag
		else:
			return self.flag

	def answer(self):
		return self.ans

def main():
	(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):
		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')
		print(*[xy[i][ts.ans[i]] for i in range(N)], sep='\n')
	else:
		print('No')
main()


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


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


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


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


(N, D) = map(int, input().split())
F = [tuple(map(int, input().split())) for i in range(N)]
EDGE = [[] for i in range(2 * N)]
EDGE_INV = [[] for i in range(2 * N)]
for i in range(N):
	(x1, y1) = F[i]
	for j in range(i, N):
		(x2, y2) = F[j]
		if abs(x1 - x2) < D and i != j:
			EDGE[i].append(N + j)
			EDGE[j].append(N + i)
			EDGE_INV[N + j].append(i)
			EDGE_INV[N + i].append(j)
		if abs(x1 - y2) < D:
			EDGE[i].append(j)
			EDGE[N + j].append(N + i)
			EDGE_INV[j].append(i)
			EDGE_INV[N + i].append(N + j)
		if abs(y1 - x2) < D:
			EDGE[N + i].append(N + j)
			EDGE[j].append(i)
			EDGE_INV[N + j].append(N + i)
			EDGE_INV[i].append(j)
		if abs(y1 - y2) < D and i != j:
			EDGE[N + i].append(j)
			EDGE[N + j].append(i)
			EDGE_INV[j].append(N + i)
			EDGE_INV[i].append(N + j)
QUE = list(range(2 * N))
check = [0] * (2 * N)
TOP_SORT = []

def dfs(x):
	if check[x] == 1:
		return
	check[x] = 1
	for to in EDGE[x]:
		if check[to] == 0:
			dfs(to)
	TOP_SORT.append(x)
	check[x] = 1
while QUE:
	x = QUE.pop()
	dfs(x)
USE = [0] * (2 * N)
SCC = []

def dfs2(x):
	Q = [x]
	USE[x] = 1
	ANS = []
	while Q:
		x = Q.pop()
		ANS.append(x)
		for to in EDGE_INV[x]:
			if USE[to] == 0:
				USE[to] = 1
				Q.append(to)
	return ANS
for x in TOP_SORT[::-1]:
	if USE[x] == 0:
		SCC.append(dfs2(x))
PLACE = [-1] * (2 * N)
for i in range(len(SCC)):
	for x in SCC[i]:
		PLACE[x] = i
ANS = [-1] * N
flag = 1
for i in range(N):
	if PLACE[i] == PLACE[N + i]:
		flag = 0
		break
	elif PLACE[i] > PLACE[N + i]:
		ANS[i] = F[i][0]
	else:
		ANS[i] = F[i][1]
if flag == 0:
	print('No')
else:
	print('Yes')
	for ans in ANS:
		print(ans)


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


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


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


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


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


from itertools import product
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 6 + 100)

class StronglyConnectedComponets:

	def __init__(self, n: int) -> None:
		self.n = n
		self.edges = [[] for _ in range(n)]
		self.rev_edeges = [[] for _ in range(n)]
		self.vs = []
		self.order = [0] * n
		self.used = [False] * n

	def add_edge(self, from_v: int, to_v: int) -> None:
		self.edges[from_v].append(to_v)
		self.rev_edeges[to_v].append(from_v)

	def dfs(self, v: int) -> None:
		self.used[v] = True
		for child in self.edges[v]:
			if not self.used[child]:
				self.dfs(child)
		self.vs.append(v)

	def rdfs(self, v: int, k: int) -> None:
		self.used[v] = True
		self.order[v] = k
		for child in self.rev_edeges[v]:
			if not self.used[child]:
				self.rdfs(child, k)

	def run(self) -> int:
		self.used = [False] * self.n
		self.vs.clear()
		for v in range(self.n):
			if not self.used[v]:
				self.dfs(v)
		self.used = [False] * self.n
		k = 0
		for v in reversed(self.vs):
			if not self.used[v]:
				self.rdfs(v, k)
				k += 1
		return k

class TwoSat(StronglyConnectedComponets):

	def __init__(self, num_var: int) -> None:
		super().__init__(2 * num_var + 1)
		self.num_var = num_var
		self.ans = []

	def add_constraint(self, a: int, b: int) -> None:
		super().add_edge(self._neg(a), self._pos(b))
		super().add_edge(self._neg(b), self._pos(a))

	def _pos(self, v: int) -> int:
		return v if v > 0 else self.num_var - v

	def _neg(self, v: int) -> int:
		return self.num_var + v if v > 0 else -v

	def run(self) -> bool:
		super().run()
		self.ans.clear()
		for i in range(self.num_var):
			if self.order[i + 1] == self.order[i + self.num_var + 1]:
				return False
			self.ans.append(self.order[i + 1] > self.order[i + self.num_var + 1])
		return True

def main() -> None:
	(N, D) = map(int, input().split())
	flags = [tuple((int(x) for x in input().split())) for _ in range(N)]
	sat = TwoSat(N)
	for (i, (x_i, y_i)) in enumerate(flags, 1):
		for (j, (x_j, y_j)) in enumerate(flags[i:], i + 1):
			if abs(x_i - x_j) < D:
				sat.add_constraint(-i, -j)
			if abs(y_i - x_j) < D:
				sat.add_constraint(i, -j)
			if abs(x_i - y_j) < D:
				sat.add_constraint(-i, j)
			if abs(y_i - y_j) < D:
				sat.add_constraint(i, j)
	if sat.run():
		print('Yes')
		print(*[x_i if sat.ans[i] else y_i for (i, (x_i, y_i)) in enumerate(flags)], sep='\n')
	else:
		print('No')
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10 ** 9))
write = lambda x: sys.stdout.write(x + '\n')
(n, d) = list(map(int, input().split()))
xy = [tuple(map(int, input().split())) for _ in range(n)]

class SAT2:

	def __init__(self, n):
		self.n = n
		self.ns = [[] for _ in range(2 * n)]

	def add_clause(self, i, f, j, g):
		n = self.n
		(u0, u1) = (i, i + n) if f else (i + n, i)
		(v0, v1) = (j, j + n) if g else (j + n, j)
		self.ns[u1].append(v0)
		self.ns[v1].append(u0)

	def solve(self):
		preorder = {}
		lowlink = {}
		seen = [False] * (2 * self.n)
		scc_queue = []
		i = 0
		count = 1
		for source in range(2 * self.n):
			if seen[source]:
				continue
			queue = [source]
			while queue:
				v = queue[-1]
				if v not in preorder:
					i = i + 1
					preorder[v] = i
				done = True
				for w in self.ns[v]:
					if w not in preorder:
						queue.append(w)
						done = False
						break
				if done:
					lowlink[v] = preorder[v]
					for w in self.ns[v]:
						if seen[w]:
							continue
						if preorder[w] > preorder[v]:
							lowlink[v] = min([lowlink[v], lowlink[w]])
						else:
							lowlink[v] = min([lowlink[v], preorder[w]])
					queue.pop()
					if lowlink[v] == preorder[v]:
						scc = {v}
						while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
							k = scc_queue.pop()
							scc.add(k)
						for v in scc:
							seen[v] = count
						count += 1
					else:
						scc_queue.append(v)
		ans = [None] * self.n
		for i in range(self.n):
			if seen[i] == seen[i + self.n]:
				return None
			elif seen[i] > seen[i + self.n]:
				ans[i] = False
			else:
				ans[i] = True
		return ans
solver = SAT2(n)
for i in range(n):
	for j in range(i + 1, n):
		if abs(xy[i][0] - xy[j][0]) < d:
			solver.add_clause(i, False, j, False)
		if abs(xy[i][0] - xy[j][1]) < d:
			solver.add_clause(i, False, j, True)
		if abs(xy[i][1] - xy[j][0]) < d:
			solver.add_clause(i, True, j, False)
		if abs(xy[i][1] - xy[j][1]) < d:
			solver.add_clause(i, True, j, True)
ans = solver.solve()
if ans is not None:
	print('Yes')
	write('\n'.join(map(str, [xy[i][0 if ans[i] else 1] for i in range(n)])))
else:
	print('No')


class two_sat:

	def __init__(self, n: int):
		self._n = n
		self.scc = scc_graph(2 * n)
		self._answer = [False] * n

	def add_clause(self, i: int, f: bool, j: int, g: bool):
		assert 0 <= i and i < self._n
		assert 0 <= j and 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) -> bool:
		_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

class csr:

	def __init__(self, n: int, edges: list):
		from copy import deepcopy
		self.start = [0] * (n + 1)
		self.elist = [[] for _ in range(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 = deepcopy(self.start)
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class scc_graph:
	edges = []

	def __init__(self, n: int):
		self._n = n
		self.now_ord = 0
		self.group_num = 0

	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)
		visited = []
		low = [0] * self._n
		ord = [-1] * self._n
		ids = [0] * self._n

		def dfs(s, v: int):
			low[v] = ord[v] = self.now_ord
			self.now_ord += 1
			visited.append(v)
			for i in range(g.start[v], g.start[v + 1]):
				to = g.elist[i][0]
				if ord[to] == -1:
					s(s, to)
					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] = self._n
					ids[u] = self.group_num
					if u == v:
						break
				self.group_num += 1
		for i in range(self._n):
			if ord[i] == -1:
				dfs(dfs, i)
		for i in range(self._n):
			ids[i] = self.group_num - 1 - ids[i]
		return (self.group_num, ids)

	def scc(self):
		ids = self.scc_ids()
		group_num = ids[0]
		counts = [0] * group_num
		for x in ids[1]:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for i in range(self._n):
			groups[ids[1][i]].append(i)
		return groups
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

def Main():
	(n, d) = read_ints()
	xy = [read_int_list() for _ in range(n)]
	tw = two_sat(n)
	for i in range(n):
		for j in range(i + 1, n):
			for x in range(2):
				if abs(xy[i][0] - xy[j][0]) < d:
					tw.add_clause(i, False, j, False)
				if abs(xy[i][0] - xy[j][1]) < d:
					tw.add_clause(i, False, j, True)
				if abs(xy[i][1] - xy[j][0]) < d:
					tw.add_clause(i, True, j, False)
				if abs(xy[i][1] - xy[j][1]) < d:
					tw.add_clause(i, True, j, True)
	if not tw.satisfiable():
		print('No')
		exit()
	print('Yes')
	ans = tw.answer()
	for (i, flag) in enumerate(ans):
		print(xy[i][0] if flag else xy[i][1])
Main()


import sys
sys.setrecursionlimit(10 ** 9)

def SCC(G):
	D = []
	C = [len(G) - 1]
	U = [1] * len(G)

	def DFS(x):
		if U[x]:
			U[x] = 0
			for i in range(len(G[x])):
				DFS(G[x][i])
			D.append(x)
	for i in range(len(G)):
		if U[i]:
			DFS(i)
	GR = [[] for i in range(len(G))]
	for i in range(len(G)):
		for j in range(len(G[i])):
			GR[G[i][j]].append(i)
	R = []
	U = [1] * len(G)

	def DFSR(x):
		if U[x]:
			R[-1].append(x)
			U[x] = 0
			for i in range(len(GR[x])):
				DFSR(GR[x][i])
	for i in range(len(G) - 1, -1, -1):
		if U[D[i]]:
			R.append([])
			DFSR(D[i])
	return R
(N, D) = map(int, input().split())
G = [[] for i in range(2 * N)]
X = [list(map(int, input().split())) for i in range(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(X[i][k] - X[j][l]) < D:
					G[k * N + i].append((l ^ 1) * N + j)
					G[l * N + j].append((k ^ 1) * N + i)
G = SCC(G)
C = [0] * (2 * N)
for i in range(len(G)):
	for j in range(len(G[i])):
		C[G[i][j]] = i
for i in range(N):
	if C[i] == C[i + N]:
		print('No')
		exit()
print('Yes')
for i in range(N):
	if C[i] > C[i + N]:
		print(X[i][0])
	else:
		print(X[i][1])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

class SCC:

	def __init__(self, n):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.graph_rev = [[] for _ in range(n)]
		self.already = [False] * n

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

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

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

	def second_dfs(self):
		self.already = [False] * self.n
		self.ans = []
		for n in reversed(self.order):
			if self.already[n]:
				continue
			self.already[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 UnionFind:

	def __init__(self, n):
		self.n = n
		self.par = [-1] * (n + 1)

	def find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.par[x] > self.par[y]:
			(x, y) = (y, x)
		self.par[x] += self.par[y]
		self.par[y] = x

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.par[self.find(x)]

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if root == self.find(i)]

class TwoSat:

	def __init__(self, n):
		self.n = n
		self.scc = SCC(n * 2)
		self.union = UnionFind(n * 2)

	def add_sat(self, fr, to):
		self.scc.add_edge(fr, to)

	def scc_prepare(self):
		return self.scc.scc()

	def union_prepare(self):
		for v in self.res:
			if len(v) == 1:
				continue
			for i in range(len(v) - 1):
				self.union.union(v[i], v[i + 1])

	def ts_judge(self):
		for i in range(self.n):
			if self.union.same(i, i + self.n):
				return False
		return True

	def judge(self):
		self.res = self.scc_prepare()
		self.union_prepare()
		res = self.ts_judge()
		return res

def main():
	(n, d) = map(int, input().split())
	ts = TwoSat(n * 2)
	flag = [None] * n
	for i in range(n):
		(x, y) = map(int, input().split())
		flag[i] = (x, y)
	for i in range(n):
		ts.add_sat(n * 3 + i, i)
		ts.add_sat(n * 2 + i, n + i)
	for i in range(n):
		for j in range(i + 1, n):
			if abs(flag[i][0] - flag[j][0]) < d:
				ts.add_sat(i, n * 2 + j)
				ts.add_sat(j, n * 2 + i)
				ts.add_sat(i, n + j)
				ts.add_sat(j, n + i)
			if abs(flag[i][0] - flag[j][1]) < d:
				ts.add_sat(i, j)
				ts.add_sat(i, n * 3 + j)
				ts.add_sat(n + j, n + i)
				ts.add_sat(n + j, n * 2 + i)
			if abs(flag[i][1] - flag[j][0]) < d:
				ts.add_sat(j, i)
				ts.add_sat(j, n * 3 + i)
				ts.add_sat(n + i, n + j)
				ts.add_sat(n + i, n * 2 + j)
			if abs(flag[i][1] - flag[j][1]) < d:
				ts.add_sat(i + n, j)
				ts.add_sat(i + n, j + n * 3)
				ts.add_sat(j + n, i)
				ts.add_sat(j + n, i + n * 3)
	ans = ts.judge()
	print('Yes' if ans else 'No')
	if ans:
		used = [-1] * n
		count = 0
		for lis in reversed(ts.res):
			for v in lis:
				if v >= n * 2:
					continue
				index = v if v < n else v - n
				if used[index] == -1:
					count += 1
					used[index] = v // n
				if count == n:
					break
		for i in range(n):
			print(flag[i][used[i]])
main()


import sys
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 9 + 1
MOD = 10 ** 9 + 7

def get_strongly_connected_components(edges, num_vertex):
	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 = '\n3 2\n1 4\n2 5\n0 6\n'
TEST_T1 = '\n>>> as_input(T1)\n>>> main()\nYes\n4\n2\n6\n'
T2 = '\n3 3\n1 4\n2 5\n0 6\n'
TEST_T2 = '\n>>> as_input(T2)\n>>> main()\nNo\n'

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


import types
_atcoder_code = "\n# Python port of AtCoder Library.\n\n__version__ = '0.0.1'\n"
atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)
_atcoder__scc_code = "\nimport copy\nimport sys\nimport typing\n\n\nclass CSR:\n    def __init__(\n            self, n: int, edges: typing.List[typing.Tuple[int, int]]) -> None:\n        self.start = [0] * (n + 1)\n        self.elist = [0] * len(edges)\n\n        for e in edges:\n            self.start[e[0] + 1] += 1\n\n        for i in range(1, n + 1):\n            self.start[i] += self.start[i - 1]\n\n        counter = copy.deepcopy(self.start)\n        for e in edges:\n            self.elist[counter[e[0]]] = e[1]\n            counter[e[0]] += 1\n\n\nclass SCCGraph:\n    '''\n    Reference:\n    R. Tarjan,\n    Depth-First Search and Linear Graph Algorithms\n    '''\n\n    def __init__(self, n: int) -> None:\n        self._n = n\n        self._edges = []\n\n    def num_vertices(self) -> int:\n        return self._n\n\n    def add_edge(self, from_vertex: int, to_vertex: int) -> None:\n        self._edges.append((from_vertex, to_vertex))\n\n    def scc_ids(self) -> typing.Tuple[int, typing.List[int]]:\n        g = CSR(self._n, self._edges)\n        now_ord = 0\n        group_num = 0\n        visited = []\n        low = [0] * self._n\n        order = [-1] * self._n\n        ids = [0] * self._n\n\n        sys.setrecursionlimit(max(self._n + 1000, sys.getrecursionlimit()))\n\n        def dfs(v: int) -> None:\n            nonlocal now_ord\n            nonlocal group_num\n            nonlocal visited\n            nonlocal low\n            nonlocal order\n            nonlocal ids\n\n            low[v] = now_ord\n            order[v] = now_ord\n            now_ord += 1\n            visited.append(v)\n            for i in range(g.start[v], g.start[v + 1]):\n                to = g.elist[i]\n                if order[to] == -1:\n                    dfs(to)\n                    low[v] = min(low[v], low[to])\n                else:\n                    low[v] = min(low[v], order[to])\n\n            if low[v] == order[v]:\n                while True:\n                    u = visited[-1]\n                    visited.pop()\n                    order[u] = self._n\n                    ids[u] = group_num\n                    if u == v:\n                        break\n                group_num += 1\n\n        for i in range(self._n):\n            if order[i] == -1:\n                dfs(i)\n\n        for i in range(self._n):\n            ids[i] = group_num - 1 - ids[i]\n\n        return group_num, ids\n\n    def scc(self) -> typing.List[typing.List[int]]:\n        ids = self.scc_ids()\n        group_num = ids[0]\n        counts = [0] * group_num\n        for x in ids[1]:\n            counts[x] += 1\n        groups = [[] for _ in range(group_num)]\n        for i in range(self._n):\n            groups[ids[1][i]].append(i)\n\n        return groups\n"
atcoder._scc = types.ModuleType('atcoder._scc')
exec(_atcoder__scc_code, atcoder._scc.__dict__)
_atcoder_twosat_code = "\nimport typing\n\n# import atcoder._scc\n\n\nclass TwoSAT:\n    '''\n    Reference:\n    B. Aspvall, M. Plass, and R. Tarjan,\n    A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean\n    Formulas\n    '''\n\n    def __init__(self, n: int = 0) -> None:\n        self._n = n\n        self._answer = [False] * n\n        self._scc = atcoder._scc.SCCGraph(2 * n)\n\n    def add_clause(self, i: int, f: bool, j: int, g: bool) -> None:\n        assert 0 <= i < self._n\n        assert 0 <= j < self._n\n\n        self._scc.add_edge(2 * i + (0 if f else 1), 2 * j + (1 if g else 0))\n        self._scc.add_edge(2 * j + (0 if g else 1), 2 * i + (1 if f else 0))\n\n    def satisfiable(self) -> bool:\n        scc_id = self._scc.scc_ids()[1]\n        for i in range(self._n):\n            if scc_id[2 * i] == scc_id[2 * i + 1]:\n                return False\n            self._answer[i] = scc_id[2 * i] < scc_id[2 * i + 1]\n        return True\n\n    def answer(self) -> typing.List[bool]:\n        return self._answer\n"
atcoder.twosat = types.ModuleType('atcoder.twosat')
exec(_atcoder_twosat_code, atcoder.twosat.__dict__)
atcoder.twosat.__dict__['atcoder'] = atcoder
atcoder.twosat.__dict__['atcoder._scc'] = atcoder._scc
TwoSAT = atcoder.twosat.TwoSAT
import sys

def main() -> None:
	(n, d) = map(int, sys.stdin.readline().split())
	x = [0] * n
	y = [0] * n
	for i in range(n):
		(x[i], y[i]) = map(int, sys.stdin.readline().split())
	two_sat = TwoSAT(n)
	for i in range(n):
		for j in range(i + 1, n):
			if abs(x[i] - x[j]) < d:
				two_sat.add_clause(i, False, j, False)
			if abs(x[i] - y[j]) < d:
				two_sat.add_clause(i, False, j, True)
			if abs(y[i] - x[j]) < d:
				two_sat.add_clause(i, True, j, False)
			if abs(y[i] - y[j]) < d:
				two_sat.add_clause(i, True, j, True)
	if not two_sat.satisfiable():
		print('No')
	else:
		print('Yes')
		answer = two_sat.answer()
		for i in range(n):
			if answer[i]:
				print(x[i])
			else:
				print(y[i])
main()


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


class convolution:

	def __init__(self, a: list, b: list, mod: int):
		(self.a, self.b) = (a, b)
		(self.n, self.m) = (len(a), len(b))
		self.MOD = mod
		self.g = primitive_root_constexpr(self.MOD)

	def convolution(self) -> list:
		(n, m) = (self.n, self.m)
		(a, b) = (self.a, self.b)
		if not n or not m:
			return []
		if min(n, m) <= 60:
			if n < m:
				(n, m) = (m, n)
				(a, b) = (b, a)
			ans = [0] * (n + m - 1)
			for i in range(n):
				for j in range(m):
					ans[i + j] += a[i] * b[j] % self.MOD
					ans[i + j] %= self.MOD
			return ans
		z = 1 << ceil_pow2(n + m - 1)
		a = self.resize(a, z)
		a = self.butterfly(a)
		b = self.resize(b, z)
		b = self.butterfly(b)
		for i in range(z):
			a[i] = a[i] * b[i] % self.MOD
		a = self.butterfly_inv(a)
		a = a[:n + m - 1]
		iz = self.inv(z)
		a = [x * iz % self.MOD for x in a]
		return a

	def butterfly(self, a: list) -> list:
		n = len(a)
		h = ceil_pow2(n)
		first = True
		sum_e = [0] * 30
		m = self.MOD
		if first:
			first = False
			(es, ies) = ([0] * 30, [0] * 30)
			cnt2 = bsf(m - 1)
			e = self.mypow(self.g, m - 1 >> cnt2)
			ie = self.inv(e)
			for i in range(cnt2, 1, -1):
				es[i - 2] = e
				ies[i - 2] = ie
				e = e * e % m
				ie = ie * ie % m
			now = 1
			for i in range(cnt2 - 2):
				sum_e[i] = es[i] * now % m
				now = now * ies[i] % m
		for ph in range(1, h + 1):
			w = 1 << ph - 1
			p = 1 << h - ph
			now = 1
			for s in range(w):
				offset = s << h - ph + 1
				for i in range(p):
					l = a[i + offset] % m
					r = a[i + offset + p] * now % m
					a[i + offset] = (l + r) % m
					a[i + offset + p] = (l - r) % m
				now = now * sum_e[bsf(~s)] % m
		return a

	def butterfly_inv(self, a: list) -> list:
		n = len(a)
		h = ceil_pow2(n)
		first = True
		sum_ie = [0] * 30
		m = self.MOD
		if first:
			first = False
			(es, ies) = ([0] * 30, [0] * 30)
			cnt2 = bsf(m - 1)
			e = self.mypow(self.g, m - 1 >> cnt2)
			ie = self.inv(e)
			for i in range(cnt2, 1, -1):
				es[i - 2] = e
				ies[i - 2] = ie
				e = e * e % m
				ie = ie * ie % m
			now = 1
			for i in range(cnt2 - 2):
				sum_ie[i] = ies[i] * now % m
				now = es[i] * now % m
		for ph in range(h, 0, -1):
			w = 1 << ph - 1
			p = 1 << h - ph
			inow = 1
			for s in range(w):
				offset = s << h - ph + 1
				for i in range(p):
					l = a[i + offset] % m
					r = a[i + offset + p] % m
					a[i + offset] = (l + r) % m
					a[i + offset + p] = (m + l - r) * inow % m
				inow = sum_ie[bsf(~s)] * inow % m
		return a

	@staticmethod
	def resize(array: list, sz: int) -> list:
		new_array = array + [0] * (sz - len(array))
		return new_array

	def inv(self, x: int):
		if is_prime_constexpr(self.MOD):
			assert x
			return self.mypow(x, self.MOD - 2)
		else:
			eg = inv_gcd(x)
			assert eg[0] == 1
			return eg[1]

	def mypow(self, x: int, n: int) -> int:
		assert 0 <= n
		r = 1
		m = self.MOD
		while n:
			if n & 1:
				r = r * x % m
			x = x * x % m
			n >>= 1
		return r

class dsu:

	def __init__(self, n: int):
		self._n = n
		self.parent_or_size = [-1] * self._n

	def merge(self, a: int, b: int) -> int:
		assert 0 <= a and a < self._n
		assert 0 <= b and a < self._n
		x = self.leader(a)
		y = self.leader(b)
		if x == y:
			return x
		if -self.parent_or_size[x] < -self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a: int, b: int) -> bool:
		assert 0 <= a and a < self._n
		assert 0 <= b and a < self._n
		return self.leader(a) == self.leader(b)

	def leader(self, a: int) -> int:
		assert 0 <= a and a < self._n
		if self.parent_or_size[a] < 0:
			return a
		self.parent_or_size[a] = self.leader(self.parent_or_size[a])
		return self.parent_or_size[a]

	def size(self, a: int) -> int:
		assert 0 <= a and a < self._n
		return -self.parent_or_size[self.leader(a)]

	def groups(self):
		leader_buf = [0] * self._n
		group_size = [0] * self._n
		for i in range(self._n):
			leader_buf[i] = self.leader(i)
			group_size[leader_buf[i]] += 1
		result = [[] for _ in range(self._n)]
		for i in range(self._n):
			result[leader_buf[i]].append(i)
		result = [v for v in result if v]
		return result

class fenwick_tree:

	def __init__(self, n):
		self._n = n
		self.data = [0] * n

	def add(self, p: int, x: int):
		assert 0 <= p and p <= self._n
		p += 1
		while p <= self._n:
			self.data[p - 1] += x
			p += p & -p

	def sum(self, l: int, r: int) -> int:
		assert 0 <= l and l <= r and (r <= self._n)
		return self.__sum(r) - self.__sum(l)

	def __sum(self, r: int) -> int:
		s = 0
		while r > 0:
			s += self.data[r - 1]
			r -= r & -r
		return s

def ceil_pow2(n: int) -> int:
	x = 0
	while 1 << x < n:
		x += 1
	return x

def bsf(n: int) -> int:
	return (n & -n).bit_length() - 1

def safe_mod(x: int, m: int) -> int:
	x %= m
	if x < 0:
		x += m
	return x

class barrett:

	def __init__(self, m: int):
		self._m = m
		self.im = -1 // (m + 1)

	def umod(self):
		return self._m

	def mul(self, a: int, b: int) -> int:
		z = a
		z *= b
		x = z * im >> 64
		v = z - x * self._m
		if self._m <= v:
			v += self._m
		return v

def pow_mod_constexpr(x: int, n: int, m: int) -> int:
	if m == 1:
		return 0
	_m = m
	r = 1
	y = safe_mod(x, m)
	while n:
		if n & 1:
			r = r * y % _m
		y = y * y % _m
		n >>= 1
	return r

def is_prime_constexpr(n: int) -> bool:
	if n <= 1:
		return False
	if n == 2 or n == 7 or n == 61:
		return True
	if n % 2 == 0:
		return False
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for a in [2, 7, 61]:
		t = d
		y = pow_mod_constexpr(a, t, n)
		while t != n - 1 and y != 1 and (y != n - 1):
			y = y * y % n
			t <<= 1
		if y != n - 1 and t % 2 == 0:
			return False
	return True

def inv_gcd(self, a: int, b: int) -> tuple:
	a = safe_mod(a, b)
	if a == 0:
		return (b, 0)
	s = b
	t = a
	m0 = 0
	m1 = 1
	while t:
		u = s // t
		s -= t * u
		m0 -= m1 * u
		tmp = s
		s = t
		t = tmp
		tmp = m0
		m0 = m1
		m1 = tmp
	if m0 < 0:
		m0 += b // s
	return (s, m0)

def primitive_root_constexpr(m: int) -> int:
	if m == 2:
		return 1
	if m == 167772161:
		return 3
	if m == 469762049:
		return 3
	if m == 754974721:
		return 11
	if m == 998244353:
		return 3
	divs = [0] * 20
	divs[0] = 2
	cnt = 1
	x = (m - 1) // 2
	while x % 2 == 0:
		x //= 2
	i = 3
	while i * i <= x:
		if x % i == 0:
			divs[cnt] = i
			cnt += 1
			while x % i == 0:
				x //= i
		i += 2
	if x > 1:
		divs[cnt] = x
		cnt += 1
	g = 2
	while True:
		ok = True
		for i in range(cnt):
			if pow_mod_constexpr(g, (m - 1) // div[i], m) == 1:
				ok = False
				break
		if ok:
			return g
		g += 1

class simple_queue:

	def __init__(self):
		self.payload = []
		self.pos = 0

	def size(self):
		return len(self.payload) - self.pos

	def empty(self):
		return self.pos == len(self.payload)

	def push(self, t: int):
		self.payload.append(t)

	def front(self):
		return self.payload[self.pos]

	def clear(self):
		self.payload.clear()
		pos = 0

	def pop(self):
		self.pos += 1

	def pop_front(self):
		self.pos += 1
		return self.payload[~-self.pos]

class csr:

	def __init__(self, n: int, edges: list):
		from copy import deepcopy
		self.start = [0] * (n + 1)
		self.elist = [[] for _ in range(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 = deepcopy(self.start)
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class scc_graph:
	edges = []

	def __init__(self, n: int):
		self._n = n
		self.now_ord = 0
		self.group_num = 0

	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)
		visited = []
		low = [0] * self._n
		ord = [-1] * self._n
		ids = [0] * self._n

		def dfs(s, v: int):
			low[v] = ord[v] = self.now_ord
			self.now_ord += 1
			visited.append(v)
			for i in range(g.start[v], g.start[v + 1]):
				to = g.elist[i][0]
				if ord[to] == -1:
					s(s, to)
					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] = self._n
					ids[u] = self.group_num
					if u == v:
						break
				self.group_num += 1
		for i in range(self._n):
			if ord[i] == -1:
				dfs(dfs, i)
		for i in range(self._n):
			ids[i] = self.group_num - 1 - ids[i]
		return (self.group_num, ids)

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

class lazy_segtree:

	def __init__(self, op, e, mapping, composition, id, v: list):
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.id = id
		self._n = len(v)
		self.log = ceil_pow2(self._n)
		self.size = 1 << self.log
		self.lz = [self.id()] * self.size
		self.d = [self.e()] * (2 * self.size)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		return self.d[p]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (r <= self._n)
		if l == r:
			return self.e()
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r >> i)
		(sml, smr) = (self.e(), self.e())
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p: int, f):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def apply(self, l: int, r: int, f):
		assert 0 <= l and l <= r and (r <= self._n)
		if l == r:
			return
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r - 1 >> i)
		(l2, r2) = (l, r)
		while l < r:
			if l & 1:
				self.__all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				self.__all_apply(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l2, r2)
		for i in range(1, self.log + 1):
			if l >> i << i != l:
				self.__update(l >> i)
			if r >> i << i != r:
				self.__update(r >> i)

	def max_right(self, l: int, g):
		assert 0 <= l and l <= self._n
		if l == self._n:
			return self._n
		l += self.size
		for i in range(self.log, 0, -1):
			self.__push(l >> i)
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.__push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, g):
		assert 0 <= r and r <= self._n
		if r == 0:
			return 0
		r += self.size
		for i in range(self.log, 0, -1):
			self.__push(r >> i)
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.__push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

	def __all_apply(self, k: int, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def __push(self, k: int):
		self.__all_apply(2 * k, self.lz[k])
		self.__all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.id()

def pow_mod(x: int, n: int, m: int) -> int:
	assert 0 <= n and 1 <= m
	if m == 1:
		return 0
	bt = barrett(m)
	r = 1
	y = safe_mod(x, m)
	while n:
		if n & 1:
			r = bt.mul(r, y)
		y = bt.mul(y, y)
		n >>= 1
	return n

def inv_mod(x: int, m: int) -> int:
	assert 1 <= m
	z = inv_gcd(x, m)
	assert z[0] == 1
	return z[1]

def crt(r: list, m: list) -> tuple:
	assert len(r) == len(m)
	n = len(r)
	r0 = 0
	m0 = 1
	for i in range(n):
		assert 1 <= m[i]
		r1 = safe_mod(r[i], m[i])
		m1 = m[i]
		if m0 < m1:
			(r0, r1) = (r1, r0)
			(m0, m1) = (m1, m0)
		if m0 % m1 == 0:
			if r0 % m1 != r1:
				return (0, 0)
			continue
		(g, im) = inv_gcd(m0, m1)
		u1 = m1 // g
		if (r1 - r0) % g:
			return (0, 0)
		x = (r1 - r0) // g % u1 * im % u1
		r0 += x * m0
		m0 *= u1
		if r0 < 0:
			r0 += m0
	return (r0, m0)

def floor_sum(n: int, m: int, a: int, b: int) -> int:
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += n * (b // m)
		bb %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

class mf_graph:
	numeric_limits_max = 10 ** 18

	def __init__(self, n: int):
		self._n = n
		self.g = [[] for _ in range(self._n)]
		self.pos = []

	def add_edge(self, _from: int, _to: int, cap: int) -> int:
		assert 0 <= _from and _from < self._n
		assert 0 <= _to and _to < self._n
		assert 0 <= cap
		m = len(self.pos)
		self.pos.append((_from, len(self.g[_from])))
		self.g[_from].append(self._edge(_to, len(self.g[_to]), cap))
		self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0))
		return m

	class edge:

		def __init__(s, _from: int, _to: int, cap: int, flow: int):
			s._from = _from
			s._to = _to
			s.cap = cap
			s.flow = flow

	def get_edge(self, i: int) -> edge:
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)

	def edges(self) -> list:
		m = len(self.pos)
		result = [self.get_edge(i) for i in range(m)]
		return result

	def change_edge(self, i: int, new_cap: int, new_flow: int):
		m = len(self.pos)
		assert 0 <= i and i < m
		assert 0 <= new_flow and new_flow <= new_cap
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		_e.cap = new_cap - new_flow
		_re.cap = new_flow

	def flow(self, s: int, t: int):
		return self.flow_(s, t, self.numeric_limits_max)

	def flow_(self, s: int, t: int, flow_limit: int) -> int:
		assert 0 <= s and s < self._n
		assert 0 <= t and t < self._n
		level = [0] * self._n
		it = [0] * self._n

		def bfs():
			for i in range(self._n):
				level[i] = -1
			level[s] = 0
			que = deque([s])
			while que:
				v = que.popleft()
				for e in self.g[v]:
					if e.cap == 0 or level[e.to] >= 0:
						continue
					level[e.to] = level[v] + 1
					if e.to == t:
						return
					que.append(e.to)

		def dfs(self_, v: int, up: int) -> int:
			if v == s:
				return up
			res = 0
			level_v = level[v]
			for i in range(it[v], len(self.g[v])):
				it[v] = i
				e = self.g[v][i]
				if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0:
					continue
				d = self_(self_, e.to, min(up - res, self.g[e.to][e.rev].cap))
				if d <= 0:
					continue
				self.g[v][i].cap += d
				self.g[e.to][e.rev].cap -= d
				res += d
				if res == up:
					break
			return res
		flow = 0
		while flow < flow_limit:
			bfs()
			if level[t] == -1:
				break
			for i in range(self._n):
				it[i] = 0
			while flow < flow_limit:
				f = dfs(dfs, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s: int) -> list:
		visited = [False] * self._n
		que = deque([s])
		while que:
			p = que.popleft()
			visited[p] = True
			for e in self.g[p]:
				if e.cap and (not visited[e.to]):
					visited[e.to] = True
					que.append(e.to)
		return visited

	class _edge:

		def __init__(s, to: int, rev: int, cap: int):
			s.to = to
			s.rev = rev
			s.cap = cap

class mcf_graph:
	numeric_limits_max = 10 ** 18

	def __init__(self, n: int):
		self._n = n
		self.g = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, _from: int, _to: int, cap: int, cost: int) -> int:
		assert 0 <= _from and _from < self._n
		assert 0 <= _to and _to < self._n
		m = len(self.pos)
		self.pos.append((_from, len(self.g[_from])))
		self.g[_from].append(self._edge(_to, len(self.g[_to]), cap, cost))
		self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0, -cost))
		return m

	class edge:

		def __init__(s, _from: int, _to: int, cap: int, flow: int, cost: int):
			s._from = _from
			s._to = _to
			s.cap = cap
			s.flow = flow
			s.cost = cost

	def get_edge(self, i: int) -> edge:
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)

	def edges(self) -> list:
		m = len(self.pos)
		result = [self.get_edge(i) for i in range(m)]
		return result

	def flow(self, s: int, t: int) -> edge:
		return self.flow_(s, t, self.numeric_limits_max)

	def flow_(self, s: int, t: int, flow_limit: int) -> edge:
		return self.__slope(s, t, flow_limit)[-1]

	def slope(self, s: int, t: int) -> list:
		return self.slope_(s, t, self.numeric_limits_max)

	def slope_(self, s: int, t: int, flow_limit: int) -> list:
		return self.__slope(s, t, flow_limit)

	def __slope(self, s: int, t: int, flow_limit: int) -> list:
		assert 0 <= s and s < self._n
		assert 0 <= t and t < self._n
		assert s != t
		dual = [0] * self._n
		dist = [0] * self._n
		(pv, pe) = ([-1] * self._n, [-1] * self._n)
		vis = [False] * self._n

		def dual_ref():
			for i in range(self._n):
				dist[i] = self.numeric_limits_max
				pv[i] = -1
				pe[i] = -1
				vis[i] = False

			class Q:

				def __init__(s, key: int, to: int):
					s.key = key
					s.to = to

				def __lt__(s, r):
					return s.key < r.key
			que = []
			dist[s] = 0
			heappush(que, Q(0, s))
			while que:
				v = heappop(que).to
				if vis[v]:
					continue
				vis[v] = True
				if v == t:
					break
				for i in range(len(self.g[v])):
					e = self.g[v][i]
					if vis[e.to] or not e.cap:
						continue
					cost = e.cost - dual[e.to] + dual[v]
					if dist[e.to] - dist[v] > cost:
						dist[e.to] = dist[v] + cost
						pv[e.to] = v
						pe[e.to] = i
						heappush(que, Q(dist[e.to], e.to))
			if not vis[t]:
				return False
			for v in range(self._n):
				if not vis[v]:
					continue
				dual[v] -= dist[t] - dist[v]
			return True
		flow = 0
		cost = 0
		prev_cost = -1
		result = []
		result.append((flow, cost))
		while flow < flow_limit:
			if not dual_ref():
				break
			c = flow_limit - flow
			v = t
			while v != s:
				c = min(c, self.g[pv[v]][pe[v]].cap)
				v = pv[v]
			v = t
			while v != s:
				e = self.g[pv[v]][pe[v]]
				e.cap -= c
				self.g[v][e.rev].cap += c
				v = pv[v]
			d = -dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				result.pop()
			result.append((flow, cost))
			prev_cost = cost
		return result

	class _edge:

		def __init__(s, to: int, rev: int, cap: int, cost: int):
			s.to = to
			s.rev = rev
			s.cap = cap
			s.cost = cost

class Mint:
	modint1000000007 = 1000000007
	modint998244353 = 998244353

	def __init__(self, v: int=0):
		self.m = self.modint1000000007
		self.x = v % self.__umod()

	def inv(self):
		if is_prime_constexpr(self.__umod()):
			assert self.x
			return self.pow_(self.__umod() - 2)
		else:
			eg = inv_gcd(self.x, self.m)
			assert eg[0] == 1
			return eg[2]

	def __str__(self):
		return str(self.x)

	def __le__(self, other):
		return self.x <= Mint.__get_val(other)

	def __lt__(self, other):
		return self.x < Mint.__get_val(other)

	def __ge__(self, other):
		return self.x >= Mint.__get_val(other)

	def __gt(self, other):
		return self.x > Mint.__get_val(other)

	def __eq__(self, other):
		return self.x == Mint.__get_val(other)

	def __iadd__(self, other):
		self.x += Mint.__get_val(other)
		if self.x >= self.__umod():
			self.x -= self.__umod()
		return self

	def __add__(self, other):
		_v = Mint(self.x)
		_v += other
		return _v

	def __isub__(self, other):
		self.x -= Mint.__get_val(other)
		if self.x >= self.__umod():
			self.x += self.__umod()
		return self

	def __sub__(self, other):
		_v = Mint(self.x)
		_v -= other
		return _v

	def __rsub__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v -= self
		return _v

	def __imul__(self, other):
		self.x = self.x * Mint.__get_val(other) % self.__umod()
		return self

	def __mul__(self, other):
		_v = Mint(self.x)
		_v *= other
		return _v

	def __itruediv__(self, other):
		self.x = self.x / Mint.__get_val(other) % self.__umod()
		return self

	def __truediv__(self, other):
		_v = Mint(self.x)
		_v /= other
		return _v

	def __rtruediv__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v /= self
		return _v

	def __ifloordiv__(self, other):
		other = other if isinstance(other, Mint) else Mint(other)
		self *= other.inv()
		return self

	def __floordiv__(self, other):
		_v = Mint(self.x)
		_v //= other
		return _v

	def __rfloordiv__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v //= self
		return _v

	def __pow__(self, other):
		_v = Mint(pow(self.x, Mint.__get_val(other), self.__umod()))
		return _v

	def __rpow__(self, other):
		_v = Mint(pow(Mint.__get_val(other), self.x, self.__umod()))
		return _v

	def __imod__(self, other):
		self.x %= Mint.__get_val(other)
		return self

	def __mod__(self, other):
		_v = Mint(self.x)
		_v %= other
		return _v

	def __rmod__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v %= self
		return _v

	def __ilshift__(self, other):
		self.x <<= Mint.__get_val(other)
		return self

	def __irshift__(self, other):
		self.x >>= Mint.__get_val(other)
		return self

	def __lshift__(self, other):
		_v = Mint(self.x)
		_v <<= other
		return _v

	def __rshift__(self, other):
		_v = Mint(self.x)
		_v >>= other
		return _v

	def __rlshift__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v <<= self
		return _v

	def __rrshift__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v >>= self
		return _v
	__repr__ = __str__
	__radd__ = __add__
	__rmul__ = __mul__

	def __umod(self):
		return self.m

	@staticmethod
	def __get_val(val):
		return val.x if isinstance(val, Mint) else val

	def pow_(self, n: int):
		assert 0 <= n
		x = Mint(self.x)
		r = 1
		while n:
			if n & 1:
				r *= x
			x *= x
			n >>= 1
		return r

	def val(self):
		return self.x

	def mod(self):
		return self.m

	def raw(self, v):
		x = Mint()
		x.x = v
		return x

class scc_graph_sub:

	def __init__(self, n):
		self.internal = scc_graph(n)

	def add_edge(self, _from, _to):
		n = self.internal.num_vertices()
		assert 0 <= _from and _from < n
		assert 0 <= _to and _to < n
		self.internal.add_edge(_from, _to)

	def scc(self):
		return self.internal.scc()

class segtree:

	def __init__(self, op, e, v: list):
		self._n = len(v)
		self.log = ceil_pow2(self._n)
		self.size = 1 << self.log
		self.op = op
		self.e = e
		self.d = [self.e()] * (self.size * 2)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> i)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		return self.d[p + self.size]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (r <= self._n)
		l += self.size
		r += self.size
		(sml, smr) = (self.e(), self.e())
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def max_right(self, l: int, f):
		assert 0 <= l and l <= self._n
		assert f(self.e())
		if l == self._n:
			return self._n
		l += self.size
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not f(self.op(sm, self.d[l])):
				while l < self.size:
					l = 2 * l
					if f(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, f):
		assert 0 <= r and r <= self._n
		assert f(self.e())
		if r == 0:
			return 0
		r += self.size
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not f(self.op(self.d[r], sm)):
				while r < self.size:
					r = 2 * r + 1
					if f(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

def sa_native(s: list):
	from functools import cmp_to_key

	def mycmp(r, l):
		if l == r:
			return -1
		while l < n and r < n:
			if s[l] != s[r]:
				return 1 if s[l] < s[r] else -1
			l += 1
			r += 1
		return 1 if l == n else -1
	n = len(s)
	sa = [i for i in range(n)]
	sa.sort(key=cmp_to_key(mycmp))
	return sa

def sa_doubling(s: list):
	from functools import cmp_to_key

	def mycmp(y, x):
		if rnk[x] != rnk[y]:
			return 1 if rnk[x] < rnk[y] else -1
		rx = rnk[x + k] if x + k < n else -1
		ry = rnk[y + k] if y + k < n else -1
		return 1 if rx < ry else -1
	n = len(s)
	sa = [i for i in range(n)]
	rnk = s
	tmp = [0] * n
	k = 1
	while k < n:
		sa.sort(key=cmp_to_key(mycmp))
		tmp[sa[0]] = 0
		for i in range(1, n):
			tmp[sa[i]] = tmp[sa[i - 1]]
			if mycmp(sa[i], sa[i - 1]):
				tmp[sa[i]] += 1
		(tmp, rnk) = (rnk, tmp)
		k *= 2
	return sa

def sa_is(s: list, upper: int):
	THRESHOLD_NATIVE = 10
	THRESHOLD_DOUBLING = 40
	n = len(s)
	if n == 0:
		return []
	if n == 1:
		return [0]
	if n == 2:
		if s[0] < s[1]:
			return [0, 1]
		else:
			return [1, 0]
	if n < THRESHOLD_NATIVE:
		return sa_native(s)
	if n < THRESHOLD_DOUBLING:
		return sa_doubling(s)
	sa = [0] * n
	ls = [False] * n
	for i in range(n - 2, -1, -1):
		ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
	sum_l = [0] * (upper + 1)
	sum_s = [0] * (upper + 1)
	for i in range(n):
		if not ls[i]:
			sum_s[s[i]] += 1
		else:
			sum_l[s[i] + 1] += 1
	for i in range(upper + 1):
		sum_s[i] += sum_l[i]
		if i < upper:
			sum_l[i + 1] += sum_s[i]

	def induce(lms: list):
		from copy import copy
		for i in range(n):
			sa[i] = -1
		buf = copy(sum_s)
		for d in lms:
			if d == n:
				continue
			sa[buf[s[d]]] = d
			buf[s[d]] += 1
		buf = copy(sum_l)
		sa[buf[s[n - 1]]] = n - 1
		buf[s[n - 1]] += 1
		for i in range(n):
			v = sa[i]
			if v >= 1 and (not ls[v - 1]):
				sa[buf[s[v - 1]]] = v - 1
				buf[s[v - 1]] += 1
		buf = copy(sum_l)
		for i in range(n - 1, -1, -1):
			v = sa[i]
			if v >= 1 and ls[v - 1]:
				buf[s[v - 1] + 1] -= 1
				sa[buf[s[v - 1] + 1]] = v - 1
	lms_map = [-1] * (n + 1)
	m = 0
	for i in range(1, n):
		if not ls[i - 1] and ls[i]:
			lms_map[i] = m
			m += 1
	lms = [i for i in range(1, n) if not ls[i - 1] and ls[i]]
	induce(lms)
	if m:
		sorted_lms = [v for v in sa if lms_map[v] != -1]
		rec_s = [0] * m
		rec_upper = 0
		rec_s[lms_map[sorted_lms[0]]] = 0
		for i in range(1, m):
			l = sorted_lms[i - 1]
			r = sorted_lms[i]
			end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
			end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
			same = True
			if end_l - l != end_r - r:
				same = False
			else:
				while l < end_l:
					if s[l] != s[r]:
						break
					l += 1
					r += 1
				if l == n or s[l] != s[r]:
					same = False
			if not same:
				rec_upper += 1
			rec_s[lms_map[sorted_lms[i]]] = rec_upper
		rec_sa = sa_is(rec_s, rec_upper)
		for i in range(m):
			sorted_lms[i] = lms[rec_sa[i]]
		induce(sorted_lms)
	return sa

def suffix_array(s: list, upper: int):
	assert 0 <= upper
	for d in s:
		assert 0 <= d and d <= upper
	sa = sa_is(s, upper)
	return sa

def suffix_array2(s: list):
	from functools import cmp_to_key
	n = len(s)
	idx = [i for i in range(n)]
	idx.sort(key=cmp_to_key(lambda l, r: s[l] < s[r]))
	s2 = [0] * n
	now = 0
	for i in range(n):
		if i and s[idx[i - 1]] != s[idx[i]]:
			now += 1
		s2[idx[i]] = now
	return sa_is(s2, now)

def suffix_array3(s: str):
	n = len(s)
	s2 = list(map(ord, s))
	return sa_is(s2, 255)

def lcp_array(s: list, sa: list):
	n = len(s)
	assert n >= 1
	rnk = [0] * n
	for i in range(n):
		rnk[sa[i]] = i
	lcp = [0] * (n - 1)
	h = 0
	for i in range(n):
		if h > 0:
			h -= 1
		if rnk[i] == 0:
			continue
		j = sa[rnk[i] - 1]
		while j + h < n and i + h < n:
			if s[j + h] != s[i + h]:
				break
			h += 1
		lcp[rnk[i] - 1] = h
	return lcp

def lcp_array2(s: str, sa: list):
	n = len(s)
	s2 = list(map(ord, s))
	return lcp_array(s2, sa)

def z_algorithm(s: list):
	n = len(s)
	if n == 0:
		return []
	z = [-1] * n
	z[0] = 0
	j = 0
	for i in range(1, n):
		k = z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
		while i + k < n and s[k] == s[i + k]:
			k += 1
		z[i] = k
		if j + z[j] < i + z[i]:
			j = i
	z[0] = n
	return z

def z_algorithm2(s: str):
	n = len(s)
	s2 = list(map(ord, s))
	return z_algorithm(s2)

class two_sat:

	def __init__(self, n: int):
		self._n = n
		self.scc = scc_graph(2 * n)
		self._answer = [False] * n

	def add_clause(self, i: int, f: bool, j: int, g: bool):
		assert 0 <= i and i < self._n
		assert 0 <= j and 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) -> bool:
		_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
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

def Main_A():
	(n, q) = read_ints()
	d = dsu(n)
	for _ in range(q):
		(t, u, v) = read_ints()
		if t == 0:
			d.merge(u, v)
		else:
			print(int(d.same(u, v)))

def Main_B():
	(n, q) = read_ints()
	a = read_int_list()
	fw = fenwick_tree(n)
	for (i, x) in enumerate(a):
		fw.add(i, x)
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			fw.add(query[1], query[2])
		else:
			print(fw.sum(query[1], query[2]))

def Main_C():
	for _ in range(read_int()):
		(n, m, a, b) = read_ints()
		print(floor_sum(n, m, a, b))

def Main_D():
	(n, m) = read_ints()
	grid = [list(read_str()) for _ in range(n)]
	mf = mf_graph(n * m + 2)
	start = n * m
	end = start + 1
	dir = [(1, 0), (0, 1)]
	for y in range(n):
		for x in range(m):
			if (y + x) % 2 == 0:
				mf.add_edge(start, m * y + x, 1)
			else:
				mf.add_edge(m * y + x, end, 1)
			if grid[y][x] == '.':
				for (dy, dx) in dir:
					ny = y + dy
					nx = x + dx
					if ny < n and nx < m and (grid[ny][nx] == '.'):
						(f, t) = (y * m + x, ny * m + nx)
						if (y + x) % 2:
							(f, t) = (t, f)
						mf.add_edge(f, t, 1)
	ans = mf.flow(start, end)
	for y in range(n):
		for x in range(m):
			for e in mf.g[y * m + x]:
				(to, rev, cap) = (e.to, e.rev, e.cap)
				(ny, nx) = divmod(to, m)
				if (y + x) % 2 == 0 and cap == 0 and (to != start) and (to != end) and (y * m + x != start) and (y * m + x != end):
					if y + 1 == ny:
						grid[y][x] = 'v'
						grid[ny][nx] = '^'
					elif y == ny + 1:
						grid[y][x] = '^'
						grid[ny][nx] = 'v'
					elif x + 1 == nx:
						grid[y][x] = '>'
						grid[ny][nx] = '<'
					elif x == nx + 1:
						grid[y][x] = '<'
						grid[ny][nx] = '>'
	print(ans)
	print(*[''.join(ret) for ret in grid], sep='\n')

def Main_E():
	(n, k) = read_ints()
	a = [read_int_list() for _ in range(n)]
	mcf = mcf_graph(n * 2 + 2)
	s = n * 2
	t = n * 2 + 1
	for i in range(n):
		mcf.add_edge(s, i, k, 0)
		mcf.add_edge(i + n, t, k, 0)
	mcf.add_edge(s, t, n * k, INF)
	for i in range(n):
		for j in range(n):
			mcf.add_edge(i, n + j, 1, INF - a[i][j])
	result = mcf.flow_(s, t, n * k)
	print(n * k * INF - result[1])
	grid = [['.'] * n for _ in range(n)]
	edges = mcf.edges()
	for e in edges:
		if e._from == s or e._to == t or e.flow == 0:
			continue
		grid[e._from][e._to - n] = 'X'
	print(*[''.join(g) for g in grid], sep='\n')

def Main_F():
	MOD = 998244353
	(n, m) = read_ints()
	a = read_int_list()
	b = read_int_list()
	a = [x % MOD for x in a]
	b = [x % MOD for x in b]
	cnv = convolution(a, b, MOD)
	ans = cnv.convolution()
	print(*ans)

def Main_G():
	sys.setrecursionlimit(10 ** 6)
	(n, m) = read_ints()
	scc = scc_graph(n)
	for _ in range(m):
		(a, b) = read_ints()
		scc.add_edge(a, b)
	ans = scc.scc()
	print(len(ans))
	for v in ans:
		print(len(v), ' '.join(map(str, v[::-1])))

def Main_H():
	(n, d) = read_ints()
	xy = [read_int_list() for _ in range(n)]
	tw = two_sat(n)
	for i in range(n):
		for j in range(i + 1, n):
			for x in range(2):
				if abs(xy[i][0] - xy[j][0]) < d:
					tw.add_clause(i, False, j, False)
				if abs(xy[i][0] - xy[j][1]) < d:
					tw.add_clause(i, False, j, True)
				if abs(xy[i][1] - xy[j][0]) < d:
					tw.add_clause(i, True, j, False)
				if abs(xy[i][1] - xy[j][1]) < d:
					tw.add_clause(i, True, j, True)
	if not tw.satisfiable():
		print('No')
		exit()
	print('Yes')
	ans = tw.answer()
	for (i, flag) in enumerate(ans):
		print(xy[i][0] if flag else xy[i][1])

def Main_I():
	s = read_str()
	sa = suffix_array3(s)
	ans = len(s) * (len(s) + 1) // 2
	for x in lcp_array2(s, sa):
		ans -= x
	print(ans)

def Main_J():

	def op(l, r):
		return max(l, r)

	def e():
		return -1

	def f(n):
		return n < r
	(n, q) = read_ints()
	a = read_int_list()
	seg = segtree(op, e, a)
	query = [read_ints() for _ in range(q)]
	for i in range(q):
		(t, l, r) = query[i]
		if t == 1:
			seg.set_(~-l, r)
		elif t == 2:
			print(seg.prod(~-l, r))
		else:
			print(seg.max_right(~-l, f) + 1)

def Main_K():
	p = 998244353

	def op(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return ((l1 + r1) % p << 32) + l2 + r2

	def e():
		return 0

	def mapping(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return ((l1 * r1 + l2 * r2) % p << 32) + r2

	def composition(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return (l1 * r1 % p << 32) + (l1 * r2 + l2) % p

	def id():
		return 1 << 32
	(n, q) = read_ints()
	A = read_int_list()
	A = [(x << 32) + 1 for x in A]
	seg = lazy_segtree(op, e, mapping, composition, id, A)
	ans = []
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			(l, r, b, c) = query[1:]
			seg.apply(l, r, (b << 32) + c)
		else:
			(l, r) = query[1:]
			print(seg.prod(l, r) >> 32)

def Main_L():

	def op(l: tuple, r: tuple):
		return (l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0])

	def e():
		return (0, 0, 0)

	def mapping(l: bool, r: tuple):
		if not l:
			return r
		return (r[1], r[0], r[1] * r[0] - r[2])

	def composition(l: bool, r: bool):
		return l ^ r

	def id():
		return False
	(n, q) = read_ints()
	A = read_int_list()
	query = [read_ints() for _ in range(q)]
	a = [(1, 0, 0) if i == 0 else (0, 1, 0) for i in A]
	seg = lazy_segtree(op, e, mapping, composition, id, a)
	for (t, l, r) in query:
		if t == 1:
			seg.apply(~-l, r, True)
		else:
			print(seg.prod(~-l, r)[2])
Main_H()


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


import sys
readline = sys.stdin.readline

class two_sat:

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

	def add_edge(self, t1, p1, t2, p2):
		self.Edge[(1 - t1) * self.N + p1].append((1 - t2) * self.N + p2)

	def solve(self):
		N = len(self.Edge)
		Edgeinv = [[] for _ in range(N)]
		for vn in range(N):
			for vf in self.Edge[vn]:
				Edgeinv[vf].append(vn)
		used = [False] * N
		dim = [len(self.Edge[i]) for i in range(N)]
		order = []
		for st in range(N):
			if not used[st]:
				stack = [st, 0]
				while stack:
					(vn, i) = (stack[-2], stack[-1])
					if not i and used[vn]:
						stack.pop()
						stack.pop()
					else:
						used[vn] = True
						if i < dim[vn]:
							stack[-1] += 1
							stack.append(self.Edge[vn][i])
							stack.append(0)
						else:
							stack.pop()
							order.append(stack.pop())
		res = [None] * N
		used = [False] * N
		cnt = -1
		for st in order[::-1]:
			if not used[st]:
				cnt += 1
				stack = [st]
				res[st] = cnt
				used[st] = True
				while stack:
					vn = stack.pop()
					for vf in Edgeinv[vn]:
						if not used[vf]:
							used[vf] = True
							res[vf] = cnt
							stack.append(vf)
		M = cnt + 1
		components = [[] for _ in range(M)]
		for i in range(N):
			components[res[i]].append(i)
		for i in range(self.N):
			if res[i] == res[self.N + i]:
				return -1
		used = [False] * self.N
		TF = [None] * self.N
		for c in components:
			for ci in c:
				cin = ci % self.N
				if used[cin]:
					continue
				if ci != cin:
					TF[cin] = True
				else:
					TF[cin] = False
				used[cin] = True
		return TF
(N, D) = map(int, readline().split())
TS = two_sat(2 * N)
for i in range(N):
	TS.add_edge(0, i, 1, N + i)
	TS.add_edge(0, N + i, 1, i)
Flags = [tuple(map(int, readline().split())) for _ in range(N)]
for i in range(N):
	(x, y) = Flags[i]
	for j in range(N):
		if i == j:
			continue
		(u, v) = Flags[j]
		if abs(x - u) < D:
			TS.add_edge(1, i, 0, j)
		if abs(x - v) < D:
			TS.add_edge(1, i, 0, N + j)
		if abs(y - u) < D:
			TS.add_edge(1, N + i, 0, j)
		if abs(y - v) < D:
			TS.add_edge(1, N + i, 0, N + j)
A = TS.solve()
Ans = [None] * N
if A != -1:
	print('Yes')
	for i in range(N):
		if A[i]:
			Ans[i] = Flags[i][0]
		else:
			Ans[i] = Flags[i][1]
	print('\n'.join(map(str, Ans)))
else:
	print('No')