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:
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(X[i] - Y[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(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)))

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(X[i] - Y[j]) < D:
            g.add_edge(i, ~j)
            g.add_edge(~j, i)
        if abs(Y[i] - X[i]) < 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] = Y[node]

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

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(X[i] - Y[j]) < D:
            g.add_edge(~i, j)
            g.add_edge(j, ~i)
        if abs(Y[i] - X[i]) < 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] = X[node]
            else:
                if res[~node] is None:
                    res[~node] = Y[~node]

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

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

Submission status: Wrong Answer

Solution code:
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(2 * N)
    # (X_i, Y_i) -> (2*i+1, 2*i+2) (i=0, ..., N-1) と置き換える
    # このとき 2*i+1 or 2*i+2 が成立しなければならない
    for i in range(N):
        sat.add_constraint(2*i+1, 2*i+2)

    # また，節 a, b (i != j) の距離が D 以下の場合，
    # a -> -b つまり -a or -b が成立しなければならない
    for i, (x_i, y_i) in enumerate(flags):
        for j, (x_j, y_j) in enumerate(flags[i+1:], i+1):
            if abs(x_i - x_j) < D:
                sat.add_constraint(-(2*i+1), -(2*j+1))
            if abs(y_i - x_j) < D:
                sat.add_constraint(-(2*i+2), -(2*j+1))
            if abs(x_i - y_j) < D:
                sat.add_constraint(-(2*i+1), -(2*j+2))
            if abs(y_i - y_j) < D:
                sat.add_constraint(-(2*i+2), -(2*j+2))
    if sat.run():
        print("Yes")
        print(*[x_i if sat.ans[2*i-1] else y_i for i, (x_i, y_i) in enumerate(flags)], sep="\n")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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 = []
    for _ in range(N):
        x_i, y_i = map(int, input().split())
        if abs(x_i - y_i) < D:
            print("No")
            break
        flags.append((x_i, y_i))

    sat = TwoSat(2 * N)
    # (X_i, Y_i) -> (2*i+1, 2*i+2) (i=0, ..., N-1) と置き換える
    # このとき 2*i+1 or 2*i+2 が成立しなければならない
    for i in range(N):
        sat.add_constraint(2*i+1, 2*i+2)

    # また，節 a, b (i != j) の距離が D 以下の場合，
    # a -> -b つまり -a or -b が成立しなければならない
    for i, (x_i, y_i) in enumerate(flags):
        for j, (x_j, y_j) in enumerate(flags[i+1:], i+1):
            if abs(x_i - x_j) < D:
                sat.add_constraint(-(2*i+1), -(2*j+1))
            if abs(y_i - x_j) < D:
                sat.add_constraint(-(2*i+2), -(2*j+1))
            if abs(x_i - y_j) < D:
                sat.add_constraint(-(2*i+1), -(2*j+2))
            if abs(y_i - y_j) < D:
                sat.add_constraint(-(2*i+2), -(2*j+2))
    if sat.run():
        print("Yes")
        print(*[x_i if sat.ans[2*i-1] else y_i for i, (x_i, y_i) in enumerate(flags)], sep="\n")
    else:
        print("No")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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(0 or 1)ならば、vはv_val(0 or 1)
    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 val == 0: self.start.append(u)
            self.vals[u]=val
            self.log.append(u)
            if self.__dfs(u, val):
                u += 1
                val = 0
                while u < self.n and self.vals[u] != -1: u += 1
            else:
                if not self.start: return False
                u = self.start.pop()
                val = 1
                while 1:
                    v = self.log.pop()
                    self.vals[v] = -1
                    if v == u: break
        return True

    def __dfs(self, u, val):
        for v, x in self.to[val][u]:
            if self.vals[v]==-1:
                self.vals[v]=val^x
                self.log.append(v)
                if not self.__dfs(v, val ^ x): return False
            else:
                if self.vals[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: Time Limit Exceeded

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 val == 0: self.start.append(u)
            if self.__dfs(u, val):
                u += 1
                val = 0
                while u < self.n and self.vals[u] != -1: u += 1
            else:
                if not self.start: return False
                u = self.start.pop()
                val = 1
                while 1:
                    v = self.log.pop()
                    self.vals[v] = -1
                    if v == u: break
        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: Accepted

Solution code:
N,D=map(int,input().split())
F=[tuple(map(int,input().split())) for i in range(N)]

EDGE=[[] for i in range(2*N)]
EDGE_INV=[[] for i in range(2*N)]

# 0～N : X_i
# N+1～2N: Y_i = ￢X_i

for i in range(N):
    x1,y1=F[i]

    for j in range(i,N):
        x2,y2=F[j]

        if abs(x1-x2)<D and i!=j:
            EDGE[i].append(N+j)
            EDGE[j].append(N+i)

            EDGE_INV[N+j].append(i)
            EDGE_INV[N+i].append(j)

        if abs(x1-y2)<D:
            EDGE[i].append(j)
            EDGE[N+j].append(N+i)

            EDGE_INV[j].append(i)
            EDGE_INV[N+i].append(N+j)

        if abs(y1-x2)<D:
            EDGE[N+i].append(N+j)
            EDGE[j].append(i)

            EDGE_INV[N+j].append(N+i)
            EDGE_INV[i].append(j)

        if abs(y1-y2)<D and i!=j:
            EDGE[N+i].append(j)
            EDGE[N+j].append(i)

            EDGE_INV[j].append(N+i)
            EDGE_INV[i].append(N+j)

QUE = list(range(2*N))
check=[0]*(2*N)
TOP_SORT=[]

def dfs(x):
    if check[x]==1:
        return
    check[x]=1
    
    for to in EDGE[x]:
        if check[to]==0:
            dfs(to)

    TOP_SORT.append(x) # 全ての点からDFSを行い, 帰りがけに点を答えに入れる
    check[x]=1

while QUE:
    x=QUE.pop()
    dfs(x)

USE=[0]*(2*N)
SCC=[]

def dfs2(x):
    Q=[x]
    USE[x]=1
    ANS=[]

    while Q:
        x=Q.pop()
        ANS.append(x)
        for to in EDGE_INV[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)
    return ANS

for x in TOP_SORT[::-1]:
    if USE[x]==0:
        SCC.append(dfs2(x))


PLACE=[-1]*(2*N)
for i in range(len(SCC)):
    for x in SCC[i]:
        PLACE[x]=i

ANS=[-1]*N
flag=1
for i in range(N):
    if PLACE[i]==PLACE[N+i]:
        flag=0
        break
    
    elif PLACE[i]>PLACE[N+i]:
        ANS[i]=F[i][0]
    else:
        ANS[i]=F[i][1]
    
if flag==0:
    print("No")
else:
    print("Yes")
    for ans in ANS:
        print(ans)

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input
 
def find_SCC(coupl):
    SCC, S, P = [], [], []
    depth = [0] * len(coupl)
 
    stack = list(range(len(coupl)))
    while stack:
        node = stack.pop()
        if node < 0:
            d = depth[~node] - 1
            if P[-1] > d:
                SCC.append(S[d:])
                del S[d:], P[-1]
                for node in SCC[-1]:
                    depth[node] = -1
        elif depth[node] > 0:
            while P[-1] > depth[node]:
                P.pop()
        elif depth[node] == 0:
            S.append(node)
            P.append(len(S))
            depth[node] = len(S)
            stack.append(~node)
            stack += coupl[node]
    return SCC[::-1]

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

    def _imply(self, x, y):
        """ x => y """
        self.graph[x].append(y if y >= 0 else 2 * self.n + y)

    def either(self, x, y):
        """x or y must be True"""
        self._imply(~x, y)
        self._imply(~y, x)

    def set(self, x):
        """x must be True"""
        self._imply(~x, x)

    def solve(self):
        SCC = find_SCC(self.graph)
        
        inSCC = [0] * (2 * self.n)
        for scc_ind, scc in enumerate(SCC):
            for node in scc:
                inSCC[node] = scc_ind
        
        for i in range(self.n):
            if inSCC[i] == inSCC[~i]:
                return False, None
        
        return True, [+(inSCC[i] < inSCC[~i]) for i in range(self.n)]

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0
 
n = inp[ii]; ii += 1
d = inp[ii]; ii += 1

sat = TwoSAT(n)

X = inp[ii + 0: ii + 2 * n: 2] 
Y = inp[ii + 1: ii + 2 * n: 2] 
ii += 2 * n

for i in range(n):
    for j in range(i + 1, n):
        if abs(X[i] - X[j]) < d:
            sat.either(i, j)
        
        if abs(Y[i] - Y[j]) < d:
            sat.either(~i, ~j)
        
        if abs(X[i] - Y[j]) < d:
            sat.either(i, ~j)
        
        if abs(Y[i] - X[j]) < d:
            sat.either(~i, j)

exists, solution = sat.solve()

if not exists:
    print 'No'
else:
    print 'Yes'
    print ' '.join(str(X[i] if b else Y[i]) for i, b in enumerate(solution))

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input
 
def find_SCC(coupl):
    SCC, S, P = [], [], []
    depth = [0] * len(coupl)
 
    stack = list(range(len(coupl)))
    while stack:
        node = stack.pop()
        if node < 0:
            d = depth[~node] - 1
            if P[-1] > d:
                SCC.append(S[d:])
                del S[d:], P[-1]
                for node in SCC[-1]:
                    depth[node] = -1
        elif depth[node] > 0:
            while P[-1] > depth[node]:
                P.pop()
        elif depth[node] == 0:
            S.append(node)
            P.append(len(S))
            depth[node] = len(S)
            stack.append(~node)
            stack += coupl[node]
    return SCC[::-1]

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

    def _imply(self, x, y):
        self.graph[x].append(y if y >= 0 else 2 * self.n + y)

    def either(self, x, y):
        """either x or y must be True"""
        self._imply(~x, y)
        self._imply(~y, x)

    def set(self, x):
        """x must be True"""
        self._imply(~x, x)

    def solve(self):
        SCC = find_SCC(self.graph)
        
        inSCC = [0] * (2 * self.n)
        for scc_ind, scc in enumerate(SCC):
            for node in scc:
                inSCC[node] = scc_ind
        
        for i in range(self.n):
            if inSCC[i] == inSCC[~i]:
                return False, None
        
        return True, [+(inSCC[i] < inSCC[~i]) for i in range(self.n)]

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0
 
n = inp[ii]; ii += 1
d = inp[ii]; ii += 1

sat = TwoSAT(n)

X = inp[ii + 0: ii + 2 * n: 2] 
Y = inp[ii + 1: ii + 2 * n: 2] 
ii += 2 * n

for i in range(n):
    for j in range(i + 1, n):
        
        if abs(X[i] - X[j]) < d:
            sat.either(i, j)
        
        if abs(Y[i] - Y[j]) < d:
            sat.either(~i, ~j)
        
        if abs(X[i] - Y[j]) < d:
            sat.either(i, ~j)
        
        if abs(Y[i] - X[j]) < d:
            sat.either(~i, j)

exists, solution = sat.solve()

if not exists:
    print 'No'
else:
    print 'Yes'
    print ' '.join(str(X[i] if b else Y[i]) for i, b in enumerate(solution))