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:
import sys

class SCC:
  '''
  SCC class with non-recursive DFS.
  '''
  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)
      else:
        if 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')
    
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
import sys

class SCC:
  '''
  SCC class with non-recursive DFS.
  '''
  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)
      else:
        if 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*N+i,(1^g)*N+j)
    self.scc.add_edge(g*N+j,(1^f)*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
  
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')

Submission status: Accepted

Solution code:
# Date [ 2020-09-12 10:24:21 ]
# Problem [ h.py ]
# Author Koki_tkg

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:
    # private
    edges = []
    
    # public
    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
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

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

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    SCC_LINKS = []

    def scc_init(n):
        int_list = [0]
        int_list.clear()
        links = [int_list.copy() for _ in range(n)]
        rev_links = [int_list.copy() for _ in range(n)]
        SCC_LINKS.append((links, rev_links))
        return len(SCC_LINKS) - 1

    def scc_add_link(ins, frm, to):
        links, rev_links = SCC_LINKS[ins]
        links[frm].append(to)
        rev_links[to].append(frm)

    def scc_exe(ins):
        links, rev_links = SCC_LINKS[ins]
        n = len(links)
        stack = np.zeros(n * 2, np.int64)
        checked = np.zeros(n, np.int8)
        postorder = np.zeros(n, np.int64)
        pi = 0

        for v in range(n):
            if checked[v]:
                continue

            # DFS1
            stack[0] = 0
            stack[1] = v
            si = 2
            while si > 0:
                i = stack[si - 2]
                v = stack[si - 1]
                if i == 0 and checked[v]:
                    si -= 2
                    continue
                checked[v] = 1
                l = len(links[v])
                while i < l and checked[links[v][i]] == 1:
                    i += 1
                if i == l:
                    postorder[pi] = v
                    pi += 1
                    si -= 2
                    continue
                stack[si - 2] = i + 1
                stack[si] = 0
                stack[si + 1] = links[v][i]
                si += 2

        postorder = postorder[::-1]
        checked = np.zeros(n, np.int8)
        sccs = []

        for v in postorder:
            if checked[v]:
                continue

            # DFS2
            stack[0] = v
            si = 1
            checked[v] = 1
            scc = [v]
            while si > 0:
                si -= 1
                v = stack[si]
                for u in rev_links[v]:
                    if checked[u] == 0:
                        checked[u] = 1
                        stack[si] = u
                        si += 1
                        scc.append(u)
            sccs.append(scc)

        return sccs

    def twosat_init(n):
        return scc_init(n * 2)

    def twosat_add_clause(ins, i, f, j, g):
        """ Add constraint that (Ai = f:0/1) && (Aj = g:0/1) is banned. """
        i <<= 1
        j <<= 1
        scc_add_link(ins, i + f, j + (g ^ 1))
        scc_add_link(ins, j + g, i + (f ^ 1))

    def twosat_satisfy(ins):
        """
        :return: if can satisfy [0,1,0,...], else None
        """
        n = len(SCC_LINKS[ins][0]) >> 1
        group_ids = np.full(n, -1, np.int64)
        result = np.full(n, -1, np.int8)

        sccs = scc_exe(ins)

        # Settle greedily from downstream in the topological order of scc.
        sccs.reverse()
        for g, scc in enumerate(sccs):
            for v in scc:
                i = v >> 1
                if result[i] == -1:
                    result[i] = v & 1
                    group_ids[i] = g
                elif group_ids[i] == g:
                    return None
        return result

    n = inp[0]
    d = inp[1]
    xxx = inp[2::2]
    yyy = inp[3::2]

    ins = twosat_init(n)

    for i in range(n):
        for j in range(i + 1, n):
            if abs(xxx[i] - xxx[j]) < d:
                twosat_add_clause(ins, i, 0, j, 0)
            if abs(xxx[i] - yyy[j]) < d:
                twosat_add_clause(ins, i, 0, j, 1)
            if abs(yyy[i] - xxx[j]) < d:
                twosat_add_clause(ins, i, 1, j, 0)
            if abs(yyy[i] - yyy[j]) < d:
                twosat_add_clause(ins, i, 1, j, 1)

    result = twosat_satisfy(ins)
    if result is None:
        return None

    ans = np.zeros(n, np.int64)
    for i in range(n):
        ans[i] = yyy[i] if result[i] else xxx[i]

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
if ans is None:
    print('No')
else:
    print('Yes')
    print('\n'.join(map(str, ans)))

Submission status: Accepted

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

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

import copy
import sys
sys.setrecursionlimit(1000000)
 
class csr:
  # start 頂点iまでの頂点が、矢元として現れた回数
  # elist 矢先のリストを矢元の昇順にしたもの
  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 = []
 
  # n 頂点数
  def __init__(s, n): s._n = n
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): s.edges.append([frm, [to]])
 
  # グループの個数と各頂点のグループidを返す
  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]
 
  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  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]
      # 距離が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:
import sys

sys.path.append("/home/contestant/.local/lib/python3.8/site-packages")

import networkx as nx

import io
import os


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N, D = [int(x) for x in input().split()]
XY = [[int(x) for x in input().split()] for i in range(N)]

graph = nx.DiGraph()
for i in range(2 * N):
    graph.add_node(i)

# f_i = 0 means choose x for flag i, f_i = 1 means choose y
# Node i is (f_i==0), node (i+N) is (f_i==1)
for i, (x1, y1) in enumerate(XY):
    for j in range(N):
        if i != j:
            x2, y2 = XY[j]
            if abs(x1 - x2) < D:
                # f_i==0 => f_j==1
                graph.add_edge(i, j + N)
            if abs(x1 - y2) < D:
                # f_i==0 => f_j==0
                graph.add_edge(i, j)
            if abs(y1 - x2) < D:
                # f_i==1 => f_j==1
                graph.add_edge(i + N, j + N)
            if abs(y1 - y2) < D:
                # f_i==1 => f_j==0
                graph.add_edge(i + N, j)


SCC = nx.algorithms.components.strongly_connected_components(graph)
assignment = {}
for comp in SCC:
    for x in comp:
        if (x < N and x + N in comp) or (x >= N and x - N in comp):
            print("No")
            exit()
        if x not in assignment:
            assignment[x] = True
            assignment[(x + N) % (2 * N)] = False

print("Yes")
for i in range(N):
    print(XY[i][0] if assignment[i] else XY[i][1])

Submission status: Accepted

Solution code:
import networkx as nx

import io
import os


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N, D = [int(x) for x in input().split()]
XY = [[int(x) for x in input().split()] for i in range(N)]

graph = nx.DiGraph()
for i in range(2 * N):
    graph.add_node(i)

# f_i = 0 means choose x for flag i, f_i = 1 means choose y
# Node i is (f_i==0), node (i+N) is (f_i==1)
for i, (x1, y1) in enumerate(XY):
    for j in range(N):
        if i != j:
            x2, y2 = XY[j]
            if abs(x1 - x2) < D:
                # f_i==0 => f_j==1
                graph.add_edge(i, j + N)
            if abs(x1 - y2) < D:
                # f_i==0 => f_j==0
                graph.add_edge(i, j)
            if abs(y1 - x2) < D:
                # f_i==1 => f_j==1
                graph.add_edge(i + N, j + N)
            if abs(y1 - y2) < D:
                # f_i==1 => f_j==0
                graph.add_edge(i + N, j)


SCC = nx.algorithms.components.strongly_connected_components(graph)
assignment = {}
for comp in SCC:
    for x in comp:
        if (x < N and x + N in comp) or (x >= N and x - N in comp):
            print("No")
            exit()
        if x not in assignment:
            assignment[x] = True
            assignment[(x + N) % (2 * N)] = False

print("Yes")
for i in range(N):
    print(XY[i][0] if assignment[i] else XY[i][1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

"""
TwoSat
"""

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)#x,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]])

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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):
        # (not if t1 == 0) p1 ==> (not if t2 == 0) 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')