Problem:
 Score : 100 points    Problem Statement Consider placing N flags on a line. Flags are numbered through 1 to N .  Flag i can be placed on the coordinate X_i or Y_i .
For any two different flags, the distance between them should be at least D .  Decide whether it is possible to place all N flags. If it is possible, print such a configulation.      Constraints  1 \leq N \leq 1000  0 \leq D \leq 10^9  0 \leq X_i < Y_i \leq 10^9  All values in Input are integer.         Input Input is given from Standard Input in the following format:  N  D  X_1  Y_1  X_2  Y_2  \vdots  X_N  Y_N       Output Print No if it is impossible to place N flags.  If it is possible, print Yes first.
After that, print N lines. i -th line of them should contain the coodinate of flag i .        Sample Input 1 3 2
1 4
2 5
0 6      Sample Output 1 Yes
4
2
0       Sample Input 2 3 3
1 4
2 5
0 6      Sample Output 2 No

Solution (Python):
import sys
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')

Solution (Python):
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  
        
        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")

Solution (Python):
import sys

input = sys.stdin.buffer.readline


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


if __name__ == "__main__":
    main()

Solution (Python):
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")


if __name__ == "__main__":
    main()