Problem:


Score : 100 points

Problem Statement

Consider placing N flags on a line. Flags are numbered through 1 to N.

Flag i can be placed on the coordinate X_i or Y_i.
For any two different flags, the distance between them should be at least D.

Decide whether it is possible to place all N flags. If it is possible, print such a configulation.

Constraints

1 \leq N \leq 1000

0 \leq D \leq 10^9

0 \leq X_i < Y_i \leq 10^9

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N D
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print No if it is impossible to place N flags.

If it is possible, print Yes first.
After that, print N lines. i-th line of them should contain the coodinate of flag i.

Sample Input 1

3 2
1 4
2 5
0 6

Sample Output 1

Yes
4
2
0

Sample Input 2

3 3
1 4
2 5
0 6

Sample Output 2

No



Sample input:
3 2
1 4
2 5
0 6


Sample output:
Yes
4
2
0

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include,/opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.string cimport string
from libcpp.vector cimport vector

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

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

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

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

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

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

cdef extern from "<atcoder/twosat>" namespace "atcoder":
    cdef cppclass two_sat:
        two_sat(int n)
        void add_clause(int i, bool f, int j, bool g)
        bool satisfiable()
        vector[bool] answer()
cdef class two_sat_:
    cdef two_sat *ptr
    def __cinit__(self, int n): self.ptr = new two_sat(n)
    def __dealloc__(self): del self.ptr
    cpdef void add_clause(self, int i, bool f, int j, bool g): self.ptr.add_clause(i, f, j, g)
    cpdef bool satisfiable(self): return self.ptr.satisfiable()
    cpdef vector[bool] answer(self): return self.ptr.answer()
"""

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

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

Submission status: Accepted

Solution code:
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):  # (x_i = f) V (x_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_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')

Submission status: Accepted

Solution code:
#-------最強ライブラリ2-SAT(Python)------
#最強ライブラリSCC(Python)が必要

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

  # クローズを足す
  # クローズってなに
  def add_clause(s, i, f, j, g):
    s.scc.add_edge(2 * i + (not f), 2 * j + (g))
    s.scc.add_edge(2 * j + (not g), 2 * i + (f))
  
  # 判定
  # O(n + m)
  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

  # クローズを満たす割当を返す
  # satisfiableがTrueとなった後に呼ばないと意味ない
  # O(1だよね？）
  def answer(s): return s._answer


#-------最強ライブラリここまで------


#-------最強ライブラリSCC(Python) ver83025------
import sys
sys.setrecursionlimit(1000000)

class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.g = {}
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): 
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    now_ord = group_num = 0
    visited = []
    low = [0] * s._n
    ord = [-1] * s._n
    ids = [0] * s._n
    # 再帰関数 
    def dfs(self, v, now_ord, group_num):
      low[v] = ord[v] = now_ord
      now_ord += 1
      visited.append(v)
      if v in s.g:
        for to in s.g[v]:
          if ord[to] == -1:
            now_ord, group_num = self(self, to, now_ord, group_num)
            low[v] = min(low[v], low[to])
          else:
            low[v] = min(low[v], ord[to])
      if low[v] == ord[v]:
        while True:
          u = visited.pop()
          ord[u] = s._n
          ids[u] = group_num
          if u == v: break
        group_num += 1
      return now_ord, group_num

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

  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  def scc(s):
    group_num, ids = s.scc_ids()
    counts = [0] * group_num
    for x in ids: counts[x] += 1
    groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[i]].append(i)
    return groups

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

#-------最強ライブラリここまで------

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

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

  ts = two_sat(N)

  for i in range(N):
    for j in range(i + 1, N):
      xi, yi = XY[i]
      xj, yj = XY[j]
      # 距離がD未満の組み合わせに関して、
      # 少なくとも一つは使用しない
      # → 少なくとも一つは別の座標を使用する
      # というルールを追加する
      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()

Submission status: Accepted

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

Submission status: Accepted

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

sys.setrecursionlimit(10**7)

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

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

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

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

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

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

		return self.dag_v_to_num, self.dag_num_to_v


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

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

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

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

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

Submission status: Accepted

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

sys.setrecursionlimit(10**7)

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

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

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

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

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

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

		return self.dag_v_to_num, self.dag_num_to_v


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

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

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

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

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

Submission status: Accepted

Solution code:
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 # 0 -> 1 -> 2
    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 = []
    ### ID が必要なとき
    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

    ### ↓ Edge が必要なとき （上の return を消す）
    nE = [set() for _ in range(len(SCC))]
    for i, e in enumerate(E):
        for j in e:
            if I[i] == I[j]: continue
            # print("i, j, I[i], I[j] =", i, j, I[i], I[j])
            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")

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


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

    # compressed[v]: 縮約後のグラフで縮約前のvが属する頂点
    # num: 縮約後のグラフの頂点数
    # 縮約後のグラフの頂点番号はトポロジカル順
    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

    # 縮約後のグラフを構築
    # 先にSCC()を実行して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

        # (a == a_bool) or (b = b_bool)というクローズを追加
        # a, b は1-indexed
        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

        # 直前に読んだsatisfiableの割り当てを返す
        # 長さN+1のbool値の配列を返す
        def answer(self):
            assert self.compressed is not None
            ret = [True] * (self.N + 1)
            for i in range(1, self.N + 1):
                if self.compressed[i] < self.compressed[i + self.N]:
                    ret[i] = False
            return ret

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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