Problem:


Score : 400 points

Problem Statement

On a two-dimensional plane, there are N red points and N blue points.
The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).

A red point and a blue point can form a friendly pair when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.

At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

Constraints

All input values are integers.

1 \leq N \leq 100

0 \leq a_i, b_i, c_i, d_i < 2N

a_1, a_2, ..., a_N, c_1, c_2, ..., c_N are all different.

b_1, b_2, ..., b_N, d_1, d_2, ..., d_N are all different.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
:
a_N b_N
c_1 d_1
c_2 d_2
:
c_N d_N

Output

Print the maximum number of friendly pairs.

Sample Input 1

3
2 0
3 1
1 3
4 2
0 4
5 5

Sample Output 1

2

For example, you can pair (2, 0) and (4, 2), then (3, 1) and (5, 5).

Sample Input 2

3
0 0
1 1
5 2
2 3
3 4
4 5

Sample Output 2

2

For example, you can pair (0, 0) and (2, 3), then (1, 1) and (3, 4).

Sample Input 3

2
2 2
3 3
0 0
1 1

Sample Output 3

0

It is possible that no pair can be formed.

Sample Input 4

5
0 0
7 3
2 2
4 8
1 6
8 5
6 9
5 4
9 1
3 7

Sample Output 4

5

Sample Input 5

5
0 0
1 1
5 5
6 6
7 7
2 2
3 3
4 4
8 8
9 9

Sample Output 5

4



Sample input:
3
2 0
3 1
1 3
4 2
0 4
5 5


Sample output:
2

Submission status: Accepted

Solution code:
import sys


def resolve():
    readline = sys.stdin.readline    # 1行だけ文字列にする

    N = int(readline())
    NN = 2 * N + 1

    # 青色はx座標をlistのindex,y座標をlistのvalueとして入力，赤は逆
    red = [[] for _ in [0] * NN]
    blue = [[] for _ in [0] * NN]
    for _ in [0] * N:
        a, b = map(int, readline().split())
        red[b].append(a)
    for _ in [0] * N:
        c, d = map(int, readline().split())
        blue[c].append(d)

    # 青色でvalueのy座標について降順(大きい順)でソート
    # 赤色ではvalueのx座標について降順でソート
    # これで青色はx座標は昇順(index)，y座標は降順(value)にソートされる
    # 赤色はy座標が昇順(index)，x座標が降順(value)
    for i in range(NN):
        r = red[i]
        b = blue[i]
        r.sort(reverse=True)
        b.sort(reverse=True)
        r[0:0] = [i]
        b[0:0] = [i]

    # 青点はx座標の昇順で，赤点はy座標の降順
    # 最小のxの青点で最大のyを持つ赤点を選択
    ans = 0
    flag = False
    while blue:
        cd_blue = blue.pop(0)
        c = cd_blue.pop(0)
        if cd_blue:
            for d in cd_blue:
                for ba_red in red[::-1]:
                    b = ba_red[0]
                    if ba_red[1:]:
                        for i in range(1, len(ba_red)):
                            a = ba_red[i]
                            if a <= c and b <= d:
                                ans += 1
                                del red[b][i]
                                flag = True
                                break
                        if flag:
                            break
                if flag:
                    flag = False
                    break
    print(ans)


resolve()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    red = []
    for _ in range(N):
        a, b = map(int, input().split())
        red.append((a, b))
    red_fin = set()
    blue = []
    for _ in range(N):
        c, d = map(int, input().split())
        blue.append((c, d))
    blue.sort()

    """
    解説pdfの通り、x方向に見た上で青い点に対応する赤い点の最適な物を貪欲に選べば良い。
    これが最適であることの証明は、非最適なペアリングを上述のペアリングに「「１組」」繋ぎ直しても
    ペアの個数が減らないことを見れば良い。
    （x+yが小さい順に見ればいけるかなと想定したのが外れルート。。。）
    """

    ans = 0
    for c, d in blue:
        cand = (-1, -1)
        for a, b in red:
            if a < c and b < d and cand[1] < b and (a, b) not in red_fin:
                cand = (a, b)
        if cand == (-1, -1): continue
        ans += 1
        red_fin.add(cand)
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import networkx as nx
N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N)]
CD = [[int(_) for _ in input().split()] for _ in range(N)]
G = nx.DiGraph()
for a, b in AB:
    G.add_edge(-1, a * 1000 + b, capacity=1)
for c, d in CD:
    G.add_edge(c * 1000 + d, -2, capacity=1)
for a, b in AB:
    for c, d in CD:
        if a < c and b < d:
            G.add_edge(a * 1000 + b, c * 1000 + d, capacity=1)
flow_value, flow_dict = nx.maximum_flow(G, -1, -2)
print(flow_value)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    R, B = [], []
    for i in range(n):
        R.append(list(map(int, input().split())) + [0, i])
    for _ in range(n):
        B.append(list(map(int, input().split())))
    B.sort(key = lambda x: x[0])
    ans = 0
    for b in B:
        f = list(filter(lambda x: x[0] < b[0] and x[1] < b[1] and x[2] == 0, R))
        if len(f) != 0:
            f.sort(key = lambda x: x[1], reverse = True)
            p = f[0]
            ans += 1
            R[p[3]][2] = 1
    print(ans)        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

N = int(input())
Red = [tuple(map(int, input().split())) for _ in range(N)]
Blue = [tuple(map(int, input().split())) for _ in range(N)]
Done = [False] * N
Red.sort()
Blue.sort()
Redx = []
Redy = []
ans = 0
for x, y in Red:
    Redx.append(x)
    Redy.append(y)

for x, y in Blue:
    i = bisect.bisect_left(Redx, x)
    m = -1
    num = -1
    for j in range(i):
        if Redy[j] >= y or Done[j]:
            continue
        if Redy[j] > m:
            m = Redy[j]
            num = j
    if num != -1:
        ans += 1
        Done[num] = True
print(ans)

Submission status: Accepted

Solution code:
#####################################################################################################
##### 最大二部マッチング問題
#####################################################################################################

"""

参考（コード）
https://kopricky.github.io/code/For_Python/bipartite_matching.html
参考（最大フロー問題）
http://nw.tsuda.ac.jp/class/algoC/c9.html
https://ikatakos.com/pot/programming_algorithm/graph_theory/maximum_flow
http://vartkw.hatenablog.com/entry/2016/12/02/002703
参考（計算量）
https://ta1sa.hatenablog.com/entry/2020/04/13/123802
https://cp-algorithms.com/graph/dinic.html

ベンチマーク
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A&lang=ja
https://atcoder.jp/contests/abc091/submissions/14937663

"""

import sys
input = sys.stdin.readline
from collections import deque


class MaxFlow:
    class Edge:
        def __init__(self, to, cap, rev):
            """
            :param to:  終点ノード
            :param cap: 残された容量
            :param rev: 遂になる逆向きのエッジ（ノード to の rev 番目のエッジ）
            """
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, node_size, inf):
        self._node = node_size
        self._inf = inf
        self._level = [-1] * self._node
        self._iter = [0] * self._node
        self._graph = [[] for _ in range(self._node)]

    def add_edge(self, from_, to, cap):
        self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
        self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_]) - 1))

    def bfs(self, start):
        """
        概要: 流れる方向を大雑把に決める（※ ループ２回目以降は逆流辺の cap が正になるので逆流も可能になり、流れる方向に選択肢が出てくる。）
        入力: cap
        出力: level[v]            (※ start から v への（cap > 0 の辺のみを使った場合の）最短距離。経路が無い場合は -1)
        備考1: 最初は適当に見つかった最短経路から始めるが、ループが進むにつれて徐々に条件のきつい cap が入力として与えられるようになり、
              最終的に遠回りの経路も全て考慮した結果が得られる。
        備考2: level[sink]（最短経路長）が単調増加であるため、ステップ数 O(V) で探索が終了する。
        """
        self._level = [-1] * self._node
        next_set = deque()
        self._level[start] = 0
        next_set.append(start)
        while next_set:
            current = next_set.popleft()
            for edge in self._graph[current]:
                """ current vertex から進める候補が _graph[current] に格納されている。ここでは逆流辺（edge.rev）は考慮しない。"""
                if self._level[edge.to] < 0 < edge.cap:
                    self._level[edge.to] = self._level[current] + 1
                    next_set.append(edge.to)

    def dfs(self, start, end, flow):
        """
        概要: bfsで大雑把に決めた方向に実際に水を流してみて本当に流れるかを調べる。
        入力: level           （※ bfs で決めた方向）
        出力: cap, flowed
        内部変数: iter          (※ 探索済みかどうかをメモ)
        備考1: bfs で先に方向を決めたおかげで、ここのステップが効率化される。 O(EV)
        """
        if start == end:
            return flow
        while self._iter[start] < len(self._graph[start]):
            edge = self._graph[start][self._iter[start]]
            if edge.cap > 0 and self._level[start] < self._level[edge.to]:
                """ 二つ目の条件が bfs からの入力である水流の方向に対応 """
                flowed = self.dfs(edge.to, end, min(flow, edge.cap))
                if flowed > 0:
                    """ 水流を流すと、正方向のcapは減って、逆方向のcapは増える """
                    edge.cap -= flowed
                    self._graph[edge.to][edge.rev].cap += flowed
                    return flowed
            self._iter[start] += 1
        return 0

    def solve(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self._level[sink] < 0:
                """ sinkへの最短距離が -1 ⇒ sink にたどり着けない ⇒ 増加路が存在しないため探索終了"""
                return flow
            self._iter = [0] * self._node
            while True:
                f = self.dfs(source, sink, self._inf)
                if f == 0:
                    break
                flow += f


class Dinic:
    def __init__(self, len_X, len_Y):
        """
        soursの位置 = 0
        sinkの位置  = len_X + len_Y + 1
        capacity   = 1
        の最大フロー問題
        """
        self.len_X, self.len_Y = len_X, len_Y
        self.mf = MaxFlow(self.len_X + self.len_Y + 2, min(self.len_X, self.len_Y))
        for i in range(self.len_X):
            """ sours から部分集合Xへの各点に capacity=1 の流れを作る """
            self.mf.add_edge(0, i + 1, 1)
        for i in range(self.len_Y):
            """ 部分集合Yへの各点からsinkへの capacity=1 の流れを作る """
            self.mf.add_edge(self.len_X + i + 1, self.len_X + self.len_Y + 1, 1)

    def add_edge(self, from_, to):
        """
        :param from_: 部分集合Xの頂点　（1,...,len_X）
        :param to:    部分集合Yの頂点　（len_X + 1,...,len_X + len_Y）
        """
        self.mf.add_edge(from_ + 1, to + self.len_X + 1, 1)

    def solve(self):
        return self.mf.solve(0, self.len_X + self.len_Y + 1)

#####################################################################################

N = int(input())

X = []
Y = []
for i in range(N):
    X.append([int(i) for i in input().split()])

for i in range(N):
    Y.append([int(i) for i in input().split()])

dinic = Dinic(len(X), len(Y))

for i in range(len(X)):
    for j in range(N):
        if X[i][0] < Y[j][0] and X[i][1] < Y[j][1]:
            dinic.add_edge(i,j)


print(dinic.solve())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class Dinic:
    def __init__(self, len_X, len_Y):
        self.len_X, self.len_Y = len_X, len_Y
        self.edges = [[] for _ in range(len_X)]
        self.matched = [-1] * len_Y
        self.visited = set()

    def add_edge(self, x, y):
        self.edges[x].append(y)

    def dfs(self, x):
        """
        :param x: X側の未マッチングの頂点の1つ
        :param visited: 空のsetを渡す（外部からの呼び出し時）
        :return: 増大路が見つかればTrue
        """
        for next_x in self.edges[x]:
            if next_x in self.visited:
                continue
            self.visited.add(next_x)
            if self.matched[next_x] == -1 or self.dfs(self.matched[next_x]):
                self.matched[next_x] = x
                return True
        return False

    def solve(self):
        """ 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる """
        res = 0
        for x in range(self.len_X):
            self.visited = set()
            res += self.dfs(x)
        return res

#################################################################################################

N = int(input())

X = []
Y = []
for i in range(N):
    X.append([int(i) for i in input().split()])

for i in range(N):
    Y.append([int(i) for i in input().split()])

dinic = Dinic(len(X), len(Y))

for i in range(len(X)):
    for j in range(N):
        if X[i][0] < Y[j][0] and X[i][1] < Y[j][1]:
            dinic.add_edge(i, j)

print(dinic.solve())

Submission status: Accepted

Solution code:
class Dinic:
    def __init__(self, len_X, len_Y):
        self.len_X, self.len_Y = len_X, len_Y
        self.edges = [[] for _ in range(len_X)]
        self.matched = [-1] * len_Y
        self.visited = set()

    def add_edge(self, x, y):
        self.edges[x].append(y)

    def dfs(self, x):
        """
        :param x: X側の未マッチングの頂点の1つ
        :param visited: 空のsetを渡す（外部からの呼び出し時）
        :return: 増大路が見つかればTrue
        """
        for next_x in self.edges[x]:
            if next_x in self.visited:
                continue
            self.visited.add(next_x)
            if self.matched[next_x] == -1 or self.dfs(self.matched[next_x]):
                self.matched[next_x] = x
                return True
        return False

    def solve(self):
        res = 0
        for x in range(self.len_X):
            self.visited = set()
            res += self.dfs(x)
        return res


#################################################################################################

N = int(input())

X = []
Y = []
for i in range(N):
    X.append([int(i) for i in input().split()])

for i in range(N):
    Y.append([int(i) for i in input().split()])

dinic = Dinic(len(X), len(Y))

for i in range(len(X)):
    for j in range(N):
        if X[i][0] < Y[j][0] and X[i][1] < Y[j][1]:
            dinic.add_edge(i, j)

print(dinic.solve())

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product

N = int(input())

red_points = [tuple(map(int, input().split(' '))) for _ in range(N)]
blue_points = [tuple(map(int, input().split(' '))) for _ in range(N)]

edges = defaultdict(set)

for i, j in product(range(N), repeat=2):
    a, b = red_points[i]
    c, d = blue_points[j]

    if a < c and b < d:
        edges[i].add(j + N)
        edges[j + N].add(i)

pairs = [-1] * (2 * N)
ans = 0


def dfs(v, seen):
    seen[v] = True
    for u in edges[v]:
        w = pairs[u]
        if w < 0 or (not seen[w] and dfs(w, seen)):
            pairs[v] = u
            pairs[u] = v
            return True
    return False


for v in range(2 * N):
    if pairs[v] < 0:
        seen = [False] * (2 * N)
        if dfs(v, seen):
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc091/tasks/arc092_a

import sys
input = sys.stdin.readline
from collections import deque


class MaxFlow:
    class Edge:
        def __init__(self, to, cap, rev):
            """
            :param to:  終点ノード
            :param cap: 残された容量
            :param rev: 遂になる逆向きのエッジ（ノード to の rev 番目のエッジ）
            """
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, node_size, inf):
        self._node = node_size
        self._inf = inf
        self._level = [-1] * self._node
        self._iter = [0] * self._node
        self._graph = [[] for _ in range(self._node)]

    def add_edge(self, from_, to, cap):
        self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
        self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_]) - 1))

    def bfs(self, start):
        """
        _level: 未訪問の場合は -1, 訪問済みの場合は start からの最短距離（正容量のエッジのみを使った経路の中での）
        """
        self._level = [-1] * self._node
        next_set = deque()
        self._level[start] = 0
        next_set.append(start)
        while next_set:
            cur_vertex = next_set.popleft()
            for edge in self._graph[cur_vertex]:
                if self._level[edge.to] < 0 < edge.cap:
                    self._level[edge.to] = self._level[cur_vertex] + 1
                    next_set.append(edge.to)

    def dfs(self, cur_vertex, end_vertex, flow):
        if cur_vertex == end_vertex:
            return flow
        while self._iter[cur_vertex] < len(self._graph[cur_vertex]):
            edge = self._graph[cur_vertex][self._iter[cur_vertex]]
            if edge.cap > 0 and self._level[cur_vertex] < self._level[edge.to]:
                flowed = self.dfs(edge.to, end_vertex, min(flow, edge.cap))
                if flowed > 0:
                    edge.cap -= flowed
                    self._graph[edge.to][edge.rev].cap += flowed
                    return flowed
            self._iter[cur_vertex] += 1
        return 0

    def solve(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self._level[sink] < 0:
                """ sinkへの最短距離が -1 ⇒ sink にたどり着けない ⇒ 増加路が存在しないため探索終了"""
                return flow
            self._iter = [0] * self._node
            while True:
                f = self.dfs(source, sink, self._inf)
                if f == 0:
                    break
                flow += f


class Dinic:
    def __init__(self, len_X, len_Y):
        """
        soursの位置 = 0
        sinkの位置  = len_X + len_Y + 1
        capacity   = 1
        の最大フロー問題
        """
        self.len_X, self.len_Y = len_X, len_Y
        self.mf = MaxFlow(self.len_X + self.len_Y + 2, min(self.len_X, self.len_Y))
        for i in range(self.len_X):
            """ sours から部分集合Xへの各点に capacity=1 の流れを作る """
            self.mf.add_edge(0, i + 1, 1)
        for i in range(self.len_Y):
            """ 部分集合Yへの各点からsinkへの capacity=1 の流れを作る """
            self.mf.add_edge(self.len_X + i + 1, self.len_X + self.len_Y + 1, 1)

    def add_edge(self, from_, to):
        """
        :param from_: 部分集合Xの頂点　（1,...,len_X）
        :param to:    部分集合Yの頂点　（len_X + 1,...,len_X + 1 + len_Y）
        """
        self.mf.add_edge(from_ + 1, to + self.len_X + 1, 1)

    def solve(self):
        return self.mf.solve(0, self.len_X + self.len_Y + 1)

#####################################################################################

N = int(input())

X = []
Y = []
for i in range(N):
    X.append([int(i) for i in input().split()])

for i in range(N):
    Y.append([int(i) for i in input().split()])

dinic = Dinic(len(X), len(Y))

for i in range(len(X)):
    for j in range(N):
        if X[i][0] < Y[j][0] and X[i][1] < Y[j][1]:
            dinic.add_edge(i,j)


print(dinic.solve())

Submission status: Accepted

Solution code:
N = int(input())
AB = []
CD = []
for i in range(N):
    AB.append(list(map(int,input().split())))
for i in range(N):
    CD.append(list(map(int,input().split())))

CD.sort(key=lambda x:x[0])

cnt = 0
RedDone = [0]*N
for i in range(N):
    Blue = CD[i]
    box = []
    for j in range(N):
        Red = AB[j]
        if Red[0]<Blue[0] and Red[1]<Blue[1] and RedDone[j]==0:
            box.append([Red[0],Red[1],j])
    if len(box)>0:
        maxy = -1
        cand = -1
        for k in range(len(box)):
            if RedDone[box[k][2]]==0:
                if maxy<box[k][1]:
                    cand = box[k][2]
                    maxy = box[k][1]
        cnt += 1
        RedDone[cand]=1
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque


class MaxFlow:
    class Edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, node_size, inf):
        self._node = node_size
        self._inf = inf
        self._level = [-1] * self._node
        self._iter = [0] * self._node
        self._graph = [[] for _ in range(self._node)]

    def add_edge(self, from_, to, cap):
        self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
        self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_]) - 1))

    def bfs(self, start):
        self._level = [-1] * self._node
        que = deque()
        self._level[start] = 0
        que.append(start)
        while que:
            cur_vertex = que.popleft()
            for e in self._graph[cur_vertex]:
                if self._level[e.to] < 0 < e.cap:
                    self._level[e.to] = self._level[cur_vertex] + 1
                    que.append(e.to)

    def dfs(self, cur_vertex, end_vertex, flow):
        if cur_vertex == end_vertex:
            return flow
        while self._iter[cur_vertex] < len(self._graph[cur_vertex]):
            e = self._graph[cur_vertex][self._iter[cur_vertex]]
            if e.cap > 0 and self._level[cur_vertex] < self._level[e.to]:
                flowed = self.dfs(e.to, end_vertex, min(flow, e.cap))
                if flowed > 0:
                    e.cap -= flowed
                    self._graph[e.to][e.rev].cap += flowed
                    return flowed
            self._iter[cur_vertex] += 1
        return 0

    def solve(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self._level[sink] < 0:
                return flow
            self._iter = [0] * self._node
            while True:
                f = self.dfs(source, sink, self._inf)
                if f == 0:
                    break
                flow += f


class BipartiteMatching:
    def __init__(self, size1, size2):
        self._u_size, self._v_size = size1, size2
        self.mf = MaxFlow(self._u_size + self._v_size + 2, min(self._u_size, self._v_size))
        for i in range(self._u_size):
            self.mf.add_edge(0, i + 1, 1)
        for i in range(self._v_size):
            self.mf.add_edge(self._u_size + i + 1, self._u_size + self._v_size + 1, 1)

    def add_edge(self, from_, to):
        self.mf.add_edge(from_ + 1, to + self._u_size + 1, 1)

    def solve(self):
        return self.mf.solve(0, self._u_size + self._v_size + 1)

#####################################################################################

N = int(input())

X = []
Y = []
for i in range(N):
    X.append([int(i) for i in input().split()])

for i in range(N):
    Y.append([int(i) for i in input().split()])

dinic = BipartiteMatching(len(X), len(Y))

for i in range(len(X)):
    for j in range(N):
        if X[i][0] < Y[j][0] and X[i][1] < Y[j][1]:
            dinic.add_edge(i,j)


print(dinic.solve())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_bipartite_matching
import numpy as np

N = int(input())

X = []
Y = []
for i in range(N):
    X.append([int(i) for i in input().split()])

for i in range(N):
    Y.append([int(i) for i in input().split()])

data = []
for i in range(len(X)):
    for j in range(N):
        if X[i][0] < Y[j][0] and X[i][1] < Y[j][1]:
            data.append([i,j,1])


if not data:
    print(0)
    exit()

edge = np.array(data, dtype = np.int64).T
# graph = csr_matrix((edge[2], (edge[:2] - 1)), (V, V))
graph = csr_matrix((edge[2], (edge[:2])), (len(X), len(Y)))           # 番号のデクリメントが不要な場合

matching = maximum_bipartite_matching(graph, perm_type="column")

print(sum(d!=-1 for d in matching))

Submission status: Accepted

Solution code:
from collections import deque


class Dinic:

    def __init__(self, N0, N1):
        self.N0 = N0
        self.N1 = N1
        self.N = N = 2+N0+N1
        self.G = [[] for i in range(N)]
        for i in range(N0):
            forward = [2+i, 1, None]
            forward[2] = backward = [0, 0, forward]
            self.G[0].append(forward)
            self.G[2+i].append(backward)
        self.backwards = bs = []
        for i in range(N1):
            forward = [1, 1, None]
            forward[2] = backward = [2+N0+i, 0, forward]
            bs.append(backward)
            self.G[2+N0+i].append(forward)
            self.G[1].append(backward)

    def add_edge(self, fr, to):
        #assert 0 <= fr < self.N0
        #assert 0 <= to < self.N1
        v0 = 2 + fr
        v1 = 2 + self.N0 + to
        forward = [v1, 1, None]
        forward[2] = backward = [v0, 0, forward]
        self.G[v0].append(forward)
        self.G[v1].append(backward)

    def bfs(self):
        G = self.G
        level = [None]*self.N
        deq = deque([0])
        level[0] = 0
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        self.level = level
        return level[1] is not None

    def dfs(self, v, t):
        if v == t:
            return 1
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w] and self.dfs(w, t):
                e[1] = 0
                rev[1] = 1
                return 1
        return 0

    def flow(self):
        flow = 0
        while self.bfs():
            *self.it, = map(iter, self.G)
            while self.dfs(0, 1):
                flow += 1
        return flow

    def matching(self):
        return [cap for _, cap, _ in self.backwards]

#####################################################################################

N = int(input())

X = []
Y = []
for i in range(N):
    X.append([int(i) for i in input().split()])

for i in range(N):
    Y.append([int(i) for i in input().split()])

dinic = Dinic(len(X), len(Y))

for i in range(len(X)):
    for j in range(N):
        if X[i][0] < Y[j][0] and X[i][1] < Y[j][1]:
            dinic.add_edge(i,j)


print(dinic.flow())

Submission status: Accepted

Solution code:
from collections import deque


class Dinic:

    def __init__(self, N0, N1):
        self.N0 = N0
        self.N1 = N1
        self.N = N = 2+N0+N1
        self.G = [[] for i in range(N)]
        for i in range(N0):
            forward = [2+i, 1, None]
            forward[2] = backward = [0, 0, forward]
            self.G[0].append(forward)
            self.G[2+i].append(backward)
        self.backwards = bs = []
        for i in range(N1):
            forward = [1, 1, None]
            forward[2] = backward = [2+N0+i, 0, forward]
            bs.append(backward)
            self.G[2+N0+i].append(forward)
            self.G[1].append(backward)

    def add_edge(self, fr, to):
        #assert 0 <= fr < self.N0
        #assert 0 <= to < self.N1
        v0 = 2 + fr
        v1 = 2 + self.N0 + to
        forward = [v1, 1, None]
        forward[2] = backward = [v0, 0, forward]
        self.G[v0].append(forward)
        self.G[v1].append(backward)

    def bfs(self):
        G = self.G
        level = [None]*self.N
        deq = deque([0])
        level[0] = 0
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        self.level = level
        return level[1] is not None

    def dfs(self, v, t):
        if v == t:
            return 1
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w] and self.dfs(w, t):
                e[1] = 0
                rev[1] = 1
                return 1
        return 0

    def flow(self):
        flow = 0
        while self.bfs():
            *self.it, = map(iter, self.G)
            while self.dfs(0, 1):
                flow += 1
        return flow

    def matching(self):
        return [cap for _, cap, _ in self.backwards]

#####################################################################################

N = int(input())
s = []
ss = []
for i in range(N):
    s.append([int(i) for i in input().split()])

for i in range(N):
    ss.append([int(i) for i in input().split()])

pair = []
for i in range(len(s)):
    right = []
    for j in range(N):
        if s[j][0] < ss[i][0] and s[j][1] < ss[i][1]:
            right.append(j)
    pair.append(right)

# print(pair)

#####################################################################################


# 頂点の組u,vと辺の重みc（今回は1）からグラフ作って最大流で解くFOOOOOOOOOOOOOOOOO

V = len(pair) + N + 2  # (sとt追加)

dinic = Dinic(V, V)

for i in range(len(pair)):  # 始点s（番号0）から青い点(1から最大len(pair))への辺
    u, v, c = 0, i + 1, 1
    dinic.add_edge(u, v)

for i in range(N):  # 赤い点（len(pair)+1から最大len(pair)+n）から終点t（番号V-1）への辺
    u, v, c = i + len(pair) + 1, V - 1, 1
    dinic.add_edge(u, v)

for i in range(len(pair)):  # 青い点（番号1から最大len(pair)に振り直し）から　赤い点（番号1～100に振り直し）への辺
    for j in range(len(pair[i])):
        node1, node2 = i + 1, pair[i][j] + len(pair) + 1

        u, v, c = node1, node2, 1
        dinic.add_edge(u, v)

print(dinic.flow() - 2)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None] * self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


def main():
    N = in_n()
    ab = [tuple(in_nn()) for _ in range(N)]
    cd = [tuple(in_nn()) for _ in range(N)]

    start = 0
    goal = 2 * N + 1
    dinic = Dinic(goal + 1)
    for i in range(1, N + 1):
        dinic.add_edge(start, i, 1)
    for i in range(N + 1, 2 * N + 1):
        dinic.add_edge(i, goal, 1)

    for i in range(N):
        for j in range(N):
            a, b = ab[i]
            c, d = cd[j]
            if a < c and b < d:
                dinic.add_edge(1 + i, N + 1 + j, 1)

    ans = dinic.flow(start, goal)
    print(ans)


if __name__ == '__main__':
    main()