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: Wrong Answer

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

class TwoSat:
    def __init__(self, n):
        # to[v][u]...頂点uの値がvのときの遷移先と反転の有無
        self.n = n
        self.to = [[[] for _ in range(n)] for _ in range(2)]
        self.vals = [-1]*n
        self.log = []
        self.start = []

    # uがu_valならば、vはv_val
    def add_edge(self, u, u_val, v, v_val):
        self.to[u_val][u].append((v, u_val ^ v_val))

    # 条件を満たすかどうかをboolで返す。構成はself.valsに入る
    def satisfy(self):
        u = val = 0
        while u < self.n:
            if self.__dfs(u, val):
                if val == 0: self.start.append(u)
                u += 1
                val = 0
                while u < self.n and self.vals[u] != -1: u += 1
            else:
                if not self.start: return False
                while 1:
                    v = self.log.pop()
                    self.vals[v] = -1
                    if v == self.start[-1]: break
                u = self.start.pop()
                val = 1
        return True

    def __dfs(self, u, val):
        if self.vals[u] != -1:
            if self.vals[u] == val: return True
            return False
        self.vals[u] = val
        self.log.append(u)
        for v, x in self.to[val][u]:
            if not self.__dfs(v, val ^ x): return False
        return True

n, d = MI()
xy = LLI(n)
ts = TwoSat(n*2)
for i, (x, y) in enumerate(xy):
    ts.add_edge(i*2, 0, i*2+1, 1)
    ts.add_edge(i*2+1, 0, i*2, 1)
    ts.add_edge(i*2, 1, i*2+1, 0)
    ts.add_edge(i*2+1, 1, i*2, 0)

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*2, 1, j*2, 0)
            ts.add_edge(j*2, 1, i*2, 0)
        if abs(x1-y2) < d:
            ts.add_edge(i*2, 1, j*2+1, 0)
            ts.add_edge(j*2+1, 1, i*2, 0)
        if abs(y1-x2) < d:
            ts.add_edge(i*2+1, 1, j*2, 0)
            ts.add_edge(j*2, 1, i*2+1, 0)
        if abs(y1-y2) < d:
            ts.add_edge(i*2+1, 1, j*2+1, 0)
            ts.add_edge(j*2+1, 1, i*2+1, 0)

if ts.satisfy():
    print("Yes")
    for i in range(n):
        if ts.vals[i*2]: print(xy[i][0])
        else: print(xy[i][1])
else:
    print("No")

Submission status: Wrong Answer

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

class TwoSat:
    def __init__(self, n):
        # to[v][u]...頂点uの値がvのときの遷移先と反転の有無
        self.n=n
        self.to = [[[] for _ in range(n)] for _ in range(2)]
        self.vals = [-1]*n

    # uがu_valのとき、vはv_valであるという関係
    def add_edge(self, u, u_val, v, v_val):
        self.to[u_val][u].append((v, u_val ^ v_val))

    # 条件を満たすかどうかをboolで返す。構成はself.valsに入る
    def satisfy(self):
        for u in range(self.n):
            if self.vals[u] != -1: continue
            if self.__dfs(u, 0): continue
            if not self.__dfs(u, 1): return False
        return True

    def __dfs(self, u, val):
        if self.vals[u] != -1:
            if self.vals[u] == val: return True
            return False
        self.vals[u] = val
        for v, x in self.to[val][u]:
            if not self.__dfs(v, val ^ x):
                self.vals[u] = -1
                return False
        return True

n, d = MI()
xy = LLI(n)
ts = TwoSat(n*2)
for i, (x, y) in enumerate(xy):
    ts.add_edge(i*2, 0, i*2+1, 1)
    ts.add_edge(i*2+1, 0, i*2, 1)
    ts.add_edge(i*2, 1, i*2+1, 0)
    ts.add_edge(i*2+1, 1, i*2, 0)

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*2, 1, j*2, 0)
            ts.add_edge(j*2, 1, i*2, 0)
        if abs(x1-y2) < d:
            ts.add_edge(i*2, 1, j*2+1, 0)
            ts.add_edge(j*2+1, 1, i*2, 0)
        if abs(y1-x2) < d:
            ts.add_edge(i*2+1, 1, j*2, 0)
            ts.add_edge(j*2, 1, i*2+1, 0)
        if abs(y1-y2) < d:
            ts.add_edge(i*2+1, 1, j*2+1, 0)
            ts.add_edge(j*2+1, 1, i*2+1, 0)

if ts.satisfy():
    print("Yes")
    for i in range(n):
        if ts.vals[i*2]:print(xy[i][0])
        else:print(xy[i][1])
else:
    print("No")

Submission status: Wrong Answer

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 __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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):
        """(xi==f) and (xj==g)
        """
        n = self.n
        u0,u1 = (i,i+n) if not f else (i+n,i)
        v0,v1 = (j,j+n) if not 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  # Preorder counter
        # ans = [None]*(2*self.n)
        count = 1
        for source in range(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] = True
            else:
                ans[i] = False
        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")

Submission status: Wrong Answer

Solution code:
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):
        """(xi==f) and (xj==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  # Preorder counter
        # ans = [None]*(2*self.n)
        count = 1
        for source in range(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] = True
            else:
                ans[i] = False
        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")

Submission status: Wrong Answer

Solution code:
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):
        """(xi==f) and (xj==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  # Preorder counter
        # ans = [None]*(2*self.n)
        count = 1
        for source in range(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] = True
            else:
                ans[i] = False
        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][1 if ans[i] else 0] for i in range(n)])))
else:
    print("No")

Submission status: Wrong Answer

Solution code:
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):
        """(xi==f) and (xj==g)
        """
        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  # Preorder counter
        # ans = [None]*(2*self.n)
        count = 1
        for source in range(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)
                        # ans.append(scc)
#                         for v in scc:
#                             if v<self.n:
#                                 vv = v + self.n
#                             else:
#                                 vv = v - self.n
#                             if vv in scc:
#                                 return None
#                             if seen[vv]:
#                                 ans[vv] = True
#                                 ans[v] = False
                        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(n):
        if i==j:
            continue
        if abs(xy[i][0]-xy[j][0])<d:
            solver.add_clause(i,True,j,True)
        if abs(xy[i][0]-xy[j][1])<d:
            solver.add_clause(i,True,j,False)
        if abs(xy[i][1]-xy[j][0])<d:
            solver.add_clause(i,False,j,True)
        if abs(xy[i][1]-xy[j][1])<d:
            solver.add_clause(i,False,j,False)
ans = solver.solve()
if ans is not None:
    print("Yes")
    write("\n".join(map(str, [xy[i][1 if ans[i] else 0] for i in range(n)])))
else:
    print("No")

Submission status: Wrong Answer

Solution code:
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):
        """(xi==f) and (xj==g)
        """
        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  # Preorder counter
        ans = [None]*(2*self.n)
        for source in range(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)
                        # ans.append(scc)
                        for v in scc:
                            if v<self.n:
                                vv = v + self.n
                            else:
                                vv = v - self.n
                            if vv in scc:
                                return None
                            if seen[vv]:
                                ans[vv] = True
                                ans[v] = False
                        for v in scc:
                            seen[v] = True
                    else:
                        scc_queue.append(v)
        return ans

solver = SAT2(n)
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if abs(xy[i][0]-xy[j][0])<d:
            solver.add_clause(i,True,j,True)
        if abs(xy[i][0]-xy[j][1])<d:
            solver.add_clause(i,True,j,False)
        if abs(xy[i][1]-xy[j][0])<d:
            solver.add_clause(i,False,j,True)
        if abs(xy[i][1]-xy[j][1])<d:
            solver.add_clause(i,False,j,False)
ans = solver.solve()
if ans is not None:
    print("Yes")
    write("\n".join(map(str, [xy[i][1 if ans[i] else 0] for i in range(n)])))
else:
    print("No")

Submission status: Wrong Answer

Solution code:
from collections import deque

class Graph(): #directed
    def __init__(self, n):
        self.n = n
        self.graph = [set() for _ in range(n)]
        self.rev = [set() for _ in range(n)]
        self.deg = [0 for _ in range(n)]

    def add_edge(self, p, q):
        self.graph[p].add(q)
        self.rev[q].add(p)
        self.deg[q] += 1

    def topological_sort(self):
        deg = self.deg[:]
        res = [i for i in range(self.n) if deg[i] == 0]
        queue = deque(res)
        used = [False for _ in range(self.n)]
        while queue:
            node = queue.popleft()
            for adj in self.graph[node]:
                deg[adj] -= 1
                if deg[adj] == 0:
                    queue.append(adj)
                    res.append(adj)
        return res

    def strongry_connected(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

import sys
input = sys.stdin.buffer.readline

N, D = map(int, input().split())

X = []
Y = []

g = Graph(2 * N)

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

for i in range(N - 1):
    for j in range(i + 1, N):
        if abs(X[i] - X[j]) < D:
            g.add_edge(i, ~j)
            g.add_edge(j, ~i)
        if abs(Y[i] - X[j]) < D:
            g.add_edge(i, ~j)
            g.add_edge(~j, i)
        if abs(X[i] - Y[j]) < D:
            g.add_edge(~i, j)
            g.add_edge(j, ~i)
        if abs(Y[i] - Y[j]) < D:
            g.add_edge(~i, j)
            g.add_edge(~j, i)

group, count = g.strongry_connected()

group_to_node = [[] for _ in range(count)]

for i in range(N):
    if group[i] == group[~i]:
        print('No')
        break
    group_to_node[group[i]].append(i)
    group_to_node[group[~i]].append(~i)

else:
    print('Yes')

    comp = Graph(count)

    for i in range(2 * N):
        for j in g.graph[i]:
            if group[i] == group[j]:
                continue
            comp.add_edge(group[i], group[j])

    ts = comp.topological_sort()

    res = [None for _ in range(N)]

    for i in ts:
        for node in group_to_node[i]:
            if node >= 0:
                if res[node] is None:
                    res[node] = Y[node]
            else:
                if res[~node] is None:
                    res[~node] = X[~node]

    for i in range(N):
        if res[i] is None:
            res[i] = X[node]

    print('\n'.join(map(str, res)))