from collections import defaultdict, deque
 
class MaxFlow:
    """Ford-Fulkerson法（Edmonds-Karp: BFSで増加パス探索）"""
 
    def __init__(self, n: int):
        self.n = n
        self.graph = defaultdict(lambda: defaultdict(int))  # 容量
 
    def add_edge(self, u: int, v: int, cap: int):
        """辺を追加（有向）"""
        self.graph[u][v] += cap
 
    def bfs(self, source: int, sink: int, parent: dict) -> int:
        """BFS で増加パスを探索し、ボトルネック容量を返す"""
        visited = {source}
        queue = deque([(source, float('inf'))])
 
        while queue:
            u, flow = queue.popleft()
            for v in self.graph[u]:
                if v not in visited and self.graph[u][v] > 0:
                    visited.add(v)
                    parent[v] = u
                    new_flow = min(flow, self.graph[u][v])
                    if v == sink:
                        return new_flow
                    queue.append((v, new_flow))
 
        return 0
 
    def max_flow(self, source: int, sink: int) -> int:
        """最大流を計算 - O(VE^2)"""
        total_flow = 0
 
        while True:
            parent = {}
            path_flow = self.bfs(source, sink, parent)
 
            if path_flow == 0:
                break  # 増加パスがない → 最大流に到達
 
            total_flow += path_flow
 
            # フローの更新（残余グラフの更新）
            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow  # 順方向: 容量を減らす
                self.graph[v][u] += path_flow  # 逆方向: キャンセル可能量を増やす
                v = u
 
        return total_flow
 
# 使用例
mf = MaxFlow(6)
# s=0, A=1, B=2, C=3, D=4, t=5
mf.add_edge(0, 1, 10)  # s → A
mf.add_edge(0, 2, 10)  # s → B
mf.add_edge(1, 3, 4)   # A → C
mf.add_edge(1, 4, 8)   # A → D
mf.add_edge(2, 4, 9)   # B → D
mf.add_edge(3, 5, 10)  # C → t
mf.add_edge(4, 3, 6)   # D → C
mf.add_edge(4, 5, 10)  # D → t
 
print(mf.max_flow(0, 5))  # 19

class Dinic:
    """Dinic法 - O(V^2 E)
    二部マッチングでは O(E sqrt(V))
    """
 
    def __init__(self, n: int):
        self.n = n
        self.graph = [[] for _ in range(n)]
 
    def add_edge(self, u: int, v: int, cap: int):
        """辺の追加（逆辺も同時に追加）"""
        self.graph[u].append([v, cap, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])
 
    def bfs(self, s: int, t: int) -> bool:
        """レベルグラフを構築"""
        self.level = [-1] * self.n
        self.level[s] = 0
        queue = deque([s])
 
        while queue:
            u = queue.popleft()
            for v, cap, _ in self.graph[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    queue.append(v)
 
        return self.level[t] >= 0
 
    def dfs(self, u: int, t: int, f: int) -> int:
        """ブロッキングフローを求める"""
        if u == t:
            return f
        while self.iter[u] < len(self.graph[u]):
            v, cap, rev = self.graph[u][self.iter[u]]
            if cap > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(f, cap))
                if d > 0:
                    self.graph[u][self.iter[u]][1] -= d
                    self.graph[v][rev][1] += d
                    return d
            self.iter[u] += 1
        return 0
 
    def max_flow(self, s: int, t: int) -> int:
        """最大流を計算"""
        flow = 0
        while self.bfs(s, t):
            self.iter = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow
 
    def min_cut(self, s: int) -> list:
        """最小カットを求める（max_flow 実行後に呼ぶ）
        返り値: s 側に属する頂点のリスト
        """
        visited = [False] * self.n
        queue = deque([s])
        visited[s] = True
        while queue:
            u = queue.popleft()
            for v, cap, _ in self.graph[u]:
                if cap > 0 and not visited[v]:
                    visited[v] = True
                    queue.append(v)
        return [i for i in range(self.n) if visited[i]]
 
# 使用例
dinic = Dinic(6)
dinic.add_edge(0, 1, 10)
dinic.add_edge(0, 2, 10)
dinic.add_edge(1, 3, 4)
dinic.add_edge(1, 4, 8)
dinic.add_edge(2, 4, 9)
dinic.add_edge(3, 5, 10)
dinic.add_edge(4, 3, 6)
dinic.add_edge(4, 5, 10)
print(dinic.max_flow(0, 5))  # 19

def find_min_cut_edges(n: int, edges: list, source: int, sink: int) -> list:
    """最小カットの辺を求める"""
    dinic = Dinic(n)
    original_edges = []
 
    for u, v, cap in edges:
        edge_idx = len(dinic.graph[u])
        dinic.add_edge(u, v, cap)
        original_edges.append((u, v, cap, edge_idx))
 
    max_flow_value = dinic.max_flow(source, sink)
 
    # s 側の頂点を特定
    s_side = set(dinic.min_cut(source))
 
    # S→T の辺がカット辺
    cut_edges = []
    for u, v, cap, _ in original_edges:
        if u in s_side and v not in s_side:
            cut_edges.append((u, v, cap))
 
    return max_flow_value, cut_edges
 
edges = [(0, 1, 3), (0, 2, 5), (1, 3, 2), (2, 3, 6), (2, 1, 4)]
# s=0, A=1, B=2, t=3
flow, cuts = find_min_cut_edges(4, edges, 0, 3)
print(f"最大流: {flow}")
print(f"最小カット辺: {cuts}")

def bipartite_matching(left: int, right: int, edges: list) -> tuple:
    """二部マッチング（最大流ベース）
    left: 左側頂点数, right: 右側頂点数
    edges: [(左頂点, 右頂点), ...]
    """
    n = left + right + 2
    source = 0
    sink = n - 1
 
    dinic = Dinic(n)
 
    # source → 左側頂点（容量1）
    for i in range(left):
        dinic.add_edge(source, i + 1, 1)
 
    # 左側 → 右側（容量1）
    for l, r in edges:
        dinic.add_edge(l + 1, left + r + 1, 1)
 
    # 右側頂点 → sink（容量1）
    for j in range(right):
        dinic.add_edge(left + j + 1, sink, 1)
 
    max_matching = dinic.max_flow(source, sink)
    return max_matching
 
# Hungarian アルゴリズム（直接実装版: DFSベース）
def hungarian(n: int, m: int, adj: list) -> tuple:
    """二部マッチング（ハンガリアン法）- O(VE)
    n: 左側頂点数, m: 右側頂点数
    adj[i]: 左頂点iに隣接する右頂点のリスト
    """
    match_l = [-1] * n  # 左側のマッチ相手
    match_r = [-1] * m  # 右側のマッチ相手
 
    def dfs(u, visited):
        for v in adj[u]:
            if visited[v]:
                continue
            visited[v] = True
            # v が未マッチ or v のマッチ相手を別に移せる
            if match_r[v] == -1 or dfs(match_r[v], visited):
                match_l[u] = v
                match_r[v] = u
                return True
        return False
 
    matching = 0
    for u in range(n):
        visited = [False] * m
        if dfs(u, visited):
            matching += 1
 
    return matching, match_l, match_r
 
# 使用例: 学生(0,1,2) → プロジェクト(0,1,2)
adj = [
    [0, 1],  # 学生0 → P0, P1
    [0, 2],  # 学生1 → P0, P2
    [1, 2],  # 学生2 → P1, P2
]
count, ml, mr = hungarian(3, 3, adj)
print(f"最大マッチング: {count}")  # 3
print(f"左→右: {ml}")             # [0, 2, 1] or similar

def hopcroft_karp(n: int, m: int, adj: list) -> tuple:
    """Hopcroft-Karp法 - O(E sqrt(V))
    n: 左側頂点数, m: 右側頂点数
    adj[i]: 左頂点iに隣接する右頂点のリスト
    """
    INF = float('inf')
    match_l = [-1] * n
    match_r = [-1] * m
    dist = [0] * n
 
    def bfs():
        queue = deque()
        for u in range(n):
            if match_l[u] == -1:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = INF
 
        found = False
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                w = match_r[v]
                if w == -1:
                    found = True
                elif dist[w] == INF:
                    dist[w] = dist[u] + 1
                    queue.append(w)
        return found
 
    def dfs(u):
        for v in adj[u]:
            w = match_r[v]
            if w == -1 or (dist[w] == dist[u] + 1 and dfs(w)):
                match_l[u] = v
                match_r[v] = u
                return True
        dist[u] = INF
        return False
 
    matching = 0
    while bfs():
        for u in range(n):
            if match_l[u] == -1:
                if dfs(u):
                    matching += 1
 
    return matching, match_l, match_r
 
# 使用例
adj = [
    [0, 1],   # 左0 → 右0, 右1
    [0, 2],   # 左1 → 右0, 右2
    [1, 2],   # 左2 → 右1, 右2
]
count, ml, mr = hopcroft_karp(3, 3, adj)
print(f"最大マッチング: {count}")  # 3

def minimum_vertex_cover(n: int, m: int, adj: list) -> list:
    """二部グラフの最小頂点被覆を求める（Konig の定理）
    最小頂点被覆 = 最大マッチング（二部グラフのみ）
    返り値: 被覆に含まれる頂点のリスト
    """
    _, match_l, match_r = hungarian(n, m, adj)
 
    # 未マッチの左頂点から交互道を辿る
    visited_l = [False] * n
    visited_r = [False] * m
 
    # 未マッチの左頂点をキューに入れる
    queue = deque()
    for u in range(n):
        if match_l[u] == -1:
            queue.append(u)
            visited_l[u] = True
 
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if not visited_r[v]:
                visited_r[v] = True
                w = match_r[v]
                if w != -1 and not visited_l[w]:
                    visited_l[w] = True
                    queue.append(w)
 
    # 被覆 = 到達不能な左頂点 + 到達可能な右頂点
    cover = []
    for u in range(n):
        if not visited_l[u]:
            cover.append(('L', u))
    for v in range(m):
        if visited_r[v]:
            cover.append(('R', v))
 
    return cover

def project_assignment(students: list, projects: list,
                       preferences: dict) -> dict:
    """学生をプロジェクトに最大数割り当て"""
    n_students = len(students)
    n_projects = len(projects)
 
    student_idx = {s: i for i, s in enumerate(students)}
    project_idx = {p: i for i, p in enumerate(projects)}
 
    adj = [[] for _ in range(n_students)]
    for student, prefs in preferences.items():
        for proj in prefs:
            adj[student_idx[student]].append(project_idx[proj])
 
    count, match_l, _ = hungarian(n_students, n_projects, adj)
 
    assignment = {}
    for i, j in enumerate(match_l):
        if j != -1:
            assignment[students[i]] = projects[j]
 
    return assignment
 
students = ["Alice", "Bob", "Charlie"]
projects = ["Web", "AI", "DB"]
prefs = {
    "Alice": ["Web", "AI"],
    "Bob": ["AI", "DB"],
    "Charlie": ["Web", "DB"],
}
result = project_assignment(students, projects, prefs)
print(result)  # {'Alice': 'Web', 'Bob': 'AI', 'Charlie': 'DB'} など

def vertex_disjoint_paths(n: int, edges: list, s: int, t: int) -> int:
    """s から t への頂点素なパスの最大数
    各頂点を v_in と v_out に分割し、v_in → v_out の容量を 1 にする
    """
    # 頂点 v → v_in = 2*v, v_out = 2*v + 1
    dinic = Dinic(2 * n)
 
    for v in range(n):
        if v == s or v == t:
            dinic.add_edge(2 * v, 2 * v + 1, float('inf'))  # s, t は無制限
        else:
            dinic.add_edge(2 * v, 2 * v + 1, 1)  # 各頂点は1回のみ通過
 
    for u, v in edges:
        dinic.add_edge(2 * u + 1, 2 * v, 1)  # u_out → v_in
        dinic.add_edge(2 * v + 1, 2 * u, 1)  # v_out → u_in（無向グラフの場合）
 
    return dinic.max_flow(2 * s, 2 * t + 1)
 
# 使用例
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
print(vertex_disjoint_paths(5, edges, 0, 4))  # 2

def image_segmentation(rows: int, cols: int,
                        foreground_cost: list,
                        background_cost: list,
                        neighbor_penalty: float) -> list:
    """画像のピクセルを前景/背景に分割する最小カットベースの手法
    foreground_cost[i]: ピクセル i を前景にするコスト
    background_cost[i]: ピクセル i を背景にするコスト
    neighbor_penalty: 隣接ピクセルが異なるラベルの場合のペナルティ
    """
    n = rows * cols
    source = n      # 前景ソース
    sink = n + 1    # 背景シンク
    dinic = Dinic(n + 2)
 
    for i in range(n):
        # source → pixel: 前景コスト（背景にするとカットされる）
        dinic.add_edge(source, i, int(background_cost[i] * 100))
        # pixel → sink: 背景コスト（前景にするとカットされる）
        dinic.add_edge(i, sink, int(foreground_cost[i] * 100))
 
    # 隣接ペナルティ
    penalty = int(neighbor_penalty * 100)
    for r in range(rows):
        for c in range(cols):
            idx = r * cols + c
            for dr, dc in [(0, 1), (1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    nidx = nr * cols + nc
                    dinic.add_edge(idx, nidx, penalty)
                    dinic.add_edge(nidx, idx, penalty)
 
    dinic.max_flow(source, sink)
 
    # s 側 = 前景, t 側 = 背景
    s_side = set(dinic.min_cut(source))
    labels = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if r * cols + c in s_side:
                labels[r][c] = 1  # 前景
 
    return labels

class MinCostFlow:
    """最小費用流 (Primal-Dual / SPFA版)
    Successive Shortest Paths アルゴリズム
    """
 
    def __init__(self, n: int):
        self.n = n
        self.graph = [[] for _ in range(n)]
 
    def add_edge(self, u: int, v: int, cap: int, cost: int):
        """辺を追加 (容量 cap, 単位コスト cost)"""
        self.graph[u].append([v, cap, cost, len(self.graph[v])])
        self.graph[v].append([u, 0, -cost, len(self.graph[u]) - 1])
 
    def min_cost_flow(self, s: int, t: int, max_flow: int) -> tuple:
        """s から t に max_flow だけ流す最小コスト
        Returns: (actual_flow, total_cost) or (-1, -1) if infeasible
        """
        total_flow = 0
        total_cost = 0
 
        while total_flow < max_flow:
            # SPFA (Bellman-Ford の改良) で最短路を求める
            dist = [float('inf')] * self.n
            dist[s] = 0
            in_queue = [False] * self.n
            prev_node = [-1] * self.n
            prev_edge = [-1] * self.n
 
            queue = deque([s])
            in_queue[s] = True
 
            while queue:
                u = queue.popleft()
                in_queue[u] = False
 
                for i, (v, cap, cost, _) in enumerate(self.graph[u]):
                    if cap > 0 and dist[u] + cost < dist[v]:
                        dist[v] = dist[u] + cost
                        prev_node[v] = u
                        prev_edge[v] = i
                        if not in_queue[v]:
                            queue.append(v)
                            in_queue[v] = True
 
            if dist[t] == float('inf'):
                break  # t に到達不能
 
            # パス上のボトルネック容量
            path_flow = max_flow - total_flow
            v = t
            while v != s:
                u = prev_node[v]
                e = prev_edge[v]
                path_flow = min(path_flow, self.graph[u][e][1])
                v = u
 
            # フローの更新
            v = t
            while v != s:
                u = prev_node[v]
                e = prev_edge[v]
                self.graph[u][e][1] -= path_flow
                self.graph[v][self.graph[u][e][3]][1] += path_flow
                v = u
 
            total_flow += path_flow
            total_cost += path_flow * dist[t]
 
        return total_flow, total_cost
 
# 使用例: 最小費用で 2 単位のフローを流す
mcf = MinCostFlow(4)
# s=0, A=1, B=2, t=3
mcf.add_edge(0, 1, 2, 1)  # s→A: 容量2, コスト1
mcf.add_edge(0, 2, 2, 3)  # s→B: 容量2, コスト3
mcf.add_edge(1, 3, 1, 2)  # A→t: 容量1, コスト2
mcf.add_edge(2, 3, 2, 1)  # B→t: 容量2, コスト1
mcf.add_edge(1, 2, 1, 1)  # A→B: 容量1, コスト1
 
flow, cost = mcf.min_cost_flow(0, 3, 2)
print(f"フロー: {flow}, コスト: {cost}")
# フロー: 2, コスト: 6 (s→A→t: 1*3=3, s→A→B→t: 1*(1+1+1)=3 or similar)

def min_cost_assignment(workers: list, tasks: list,
                         costs: dict) -> tuple:
    """各ワーカーに1つのタスクを割り当て、総コストを最小化
    costs[(worker, task)] = コスト
    """
    n_workers = len(workers)
    n_tasks = len(tasks)
    worker_idx = {w: i for i, w in enumerate(workers)}
    task_idx = {t: i for i, t in enumerate(tasks)}
 
    # ネットワーク: s → workers → tasks → t
    n = n_workers + n_tasks + 2
    source = n - 2
    sink = n - 1
    mcf = MinCostFlow(n)
 
    for i in range(n_workers):
        mcf.add_edge(source, i, 1, 0)
 
    for (w, t), cost in costs.items():
        wi = worker_idx[w]
        ti = task_idx[t] + n_workers
        mcf.add_edge(wi, ti, 1, cost)
 
    for j in range(n_tasks):
        mcf.add_edge(n_workers + j, sink, 1, 0)
 
    flow, total_cost = mcf.min_cost_flow(source, sink, min(n_workers, n_tasks))
 
    return flow, total_cost
 
workers = ["Alice", "Bob", "Charlie"]
tasks = ["Task1", "Task2", "Task3"]
costs = {
    ("Alice", "Task1"): 5, ("Alice", "Task2"): 3, ("Alice", "Task3"): 7,
    ("Bob", "Task1"): 2, ("Bob", "Task2"): 6, ("Bob", "Task3"): 4,
    ("Charlie", "Task1"): 8, ("Charlie", "Task2"): 1, ("Charlie", "Task3"): 3,
}
flow, cost = min_cost_assignment(workers, tasks, costs)
print(f"割り当て数: {flow}, 総コスト: {cost}")
# 最適: Alice-Task2(3), Bob-Task1(2), Charlie-Task3(3) → 総コスト: 8

def schedule_tasks(n_workers: int, tasks: list) -> int:
    """各タスクに開始時刻・終了時刻・必要人数が設定されている
    全タスクを同時に満たすために必要な最小ワーカー数を求める
    （最大流の逆問題として解く場合もあるが、ここではフローで検証）
    """
    # 時刻を離散化
    times = set()
    for start, end, _ in tasks:
        times.add(start)
        times.add(end)
    times = sorted(times)
    time_idx = {t: i for i, t in enumerate(times)}
 
    n_times = len(times)
    source = n_times + len(tasks)
    sink = source + 1
    total_nodes = sink + 1
    dinic = Dinic(total_nodes)
 
    # 時間ノード間を繋ぐ（ワーカーの流れ）
    for i in range(n_times - 1):
        dinic.add_edge(i, i + 1, n_workers)
 
    # 各タスク: 開始時刻 → タスクノード → 終了時刻
    for task_id, (start, end, required) in enumerate(tasks):
        task_node = n_times + task_id
        si = time_idx[start]
        ei = time_idx[end]
        dinic.add_edge(si, task_node, required)
        dinic.add_edge(task_node, ei, required)
 
    # source → 最初の時刻, 最後の時刻 → sink
    dinic.add_edge(source, 0, n_workers)
    dinic.add_edge(n_times - 1, sink, n_workers)
 
    return dinic.max_flow(source, sink)

def network_reliability(n: int, edges: list, s: int, t: int) -> dict:
    """ネットワークの信頼性指標を計算
    - 辺連結度: s-t 間を切断するために必要な最小辺数
    - 頂点連結度: s-t 間を切断するために必要な最小頂点数
    """
    # 辺連結度 = 最大流（全辺容量1）
    dinic_edge = Dinic(n)
    for u, v in edges:
        dinic_edge.add_edge(u, v, 1)
        dinic_edge.add_edge(v, u, 1)
    edge_connectivity = dinic_edge.max_flow(s, t)
 
    # 頂点連結度 = 頂点分割後の最大流
    vertex_connectivity = vertex_disjoint_paths(n, edges, s, t)
 
    return {
        'edge_connectivity': edge_connectivity,
        'vertex_connectivity': vertex_connectivity,
    }
 
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (1, 2)]
result = network_reliability(4, edges, 0, 3)
print(f"辺連結度: {result['edge_connectivity']}")
print(f"頂点連結度: {result['vertex_connectivity']}")

# BAD: 残余グラフの逆辺を追加しない
def bad_add_edge(self, u, v, cap):
    self.graph[u][v] = cap
    # 逆辺 graph[v][u] = 0 を追加していない!
    # → フローのキャンセルができず、最大流が求まらない
 
# GOOD: 必ず逆辺を追加
def good_add_edge(self, u, v, cap):
    self.graph[u][v] += cap
    # 逆辺（初期容量0）を確保
    if v not in self.graph or u not in self.graph[v]:
        self.graph[v][u] += 0

# BAD: 全順列を試して最大マッチング → O(n!)
from itertools import permutations
def bad_matching(adj, n, m):
    max_match = 0
    for perm in permutations(range(m)):
        count = sum(1 for i in range(min(n,m)) if perm[i] in adj[i])
        max_match = max(max_match, count)
    return max_match  # n! は大きすぎる
 
# GOOD: ハンガリアン法 or 最大流 → O(VE) or O(V^2 E)
count, _, _ = hungarian(n, m, adj)

# BAD: BFS のたびに iter を初期化しない
def bad_max_flow(self, s, t):
    flow = 0
    self.iter = [0] * self.n  # 一度だけ初期化
    while self.bfs(s, t):
        # iter が前回の値のまま → DFS が正しく動かない
        f = self.dfs(s, t, float('inf'))
        flow += f
 
# GOOD: BFS のたびに iter を再初期化
def good_max_flow(self, s, t):
    flow = 0
    while self.bfs(s, t):
        self.iter = [0] * self.n  # 毎回初期化
        while True:
            f = self.dfs(s, t, float('inf'))
            if f == 0:
                break
            flow += f
    return flow

# BAD: 無向辺を有向辺として1回だけ追加
dinic.add_edge(u, v, cap)  # u→v のみ
 
# GOOD: 無向辺は両方向に追加
dinic.add_edge(u, v, cap)
dinic.add_edge(v, u, cap)
# ※ Dinic の add_edge は内部で逆辺（容量0）を追加しているので
# 無向辺の場合は手動で両方向の辺を追加する必要がある

# デバッグ用ユーティリティ
import logging
import traceback
from functools import wraps
 
# ロガーの設定
logging.basicConfig(
    level=logging.DEBUG,
    format='%(asctime)s [%(levelname)s] %(name)s: %(message)s'
)
logger = logging.getLogger(__name__)
 
def debug_decorator(func):
    """関数の入出力をログ出力するデコレータ"""
    @wraps(func)
    def wrapper(*args, **kwargs):
        logger.debug(f"呼び出し: {func.__name__}(args={args}, kwargs={kwargs})")
        try:
            result = func(*args, **kwargs)
            logger.debug(f"戻り値: {func.__name__} -> {result}")
            return result
        except Exception as e:
            logger.error(f"例外発生: {func.__name__}: {e}")
            logger.error(traceback.format_exc())
            raise
    return wrapper
 
@debug_decorator
def process_data(items):
    """データ処理（デバッグ対象）"""
    if not items:
        raise ValueError("空のデータ")
    return [item * 2 for item in items]

# 設計判断の記録テンプレート
class ArchitectureDecisionRecord:
    """ADR (Architecture Decision Record) の作成"""
 
    def __init__(self, title: str):
        self.title = title
        self.context = ""
        self.decision = ""
        self.consequences = []
        self.alternatives = []
 
    def set_context(self, context: str):
        """背景と課題の記述"""
        self.context = context
        return self
 
    def set_decision(self, decision: str):
        """決定内容の記述"""
        self.decision = decision
        return self
 
    def add_consequence(self, consequence: str, positive: bool = True):
        """結果の追加"""
        self.consequences.append({
            'description': consequence,
            'type': 'positive' if positive else 'negative'
        })
        return self
 
    def add_alternative(self, name: str, reason_rejected: str):
        """却下した代替案の追加"""
        self.alternatives.append({
            'name': name,
            'reason_rejected': reason_rejected
        })
        return self
 
    def to_markdown(self) -> str:
        """Markdown形式で出力"""
        md = f"# ADR: {self.title}\n\n"
        md += f"## 背景\n{self.context}\n\n"
        md += f"## 決定\n{self.decision}\n\n"
        md += "## 結果\n"
        for c in self.consequences:
            icon = "✅" if c['type'] == 'positive' else "⚠️"
            md += f"- {icon} {c['description']}\n"
        md += "\n## 却下した代替案\n"
        for a in self.alternatives:
            md += f"- **{a['name']}**: {a['reason_rejected']}\n"
        return md

class PushRelabel:
    """Push-Relabel法（FIFO選択則） - O(V^3)"""
 
    def __init__(self, n: int):
        self.n = n
        self.cap = [[0] * n for _ in range(n)]
        self.flow = [[0] * n for _ in range(n)]
 
    def add_edge(self, u: int, v: int, c: int):
        self.cap[u][v] += c
 
    def max_flow(self, s: int, t: int) -> int:
        n = self.n
        height = [0] * n
        excess = [0] * n
        height[s] = n
 
        # 初期プッシュ: s から全隣接辺を飽和
        for v in range(n):
            if self.cap[s][v] > 0:
                f = self.cap[s][v]
                self.flow[s][v] = f
                self.flow[v][s] = -f
                excess[v] = f
                excess[s] -= f
 
        # アクティブ頂点のキュー（FIFO）
        active = deque()
        in_queue = [False] * n
        for v in range(n):
            if v != s and v != t and excess[v] > 0:
                active.append(v)
                in_queue[v] = True
 
        while active:
            u = active.popleft()
            in_queue[u] = False
            self._discharge(u, s, t, height, excess, active, in_queue)
 
        return excess[t]
 
    def _discharge(self, u, s, t, height, excess, active, in_queue):
        n = self.n
        while excess[u] > 0:
            pushed = False
            for v in range(n):
                residual = self.cap[u][v] - self.flow[u][v]
                if residual > 0 and height[u] == height[v] + 1:
                    # Push
                    d = min(excess[u], residual)
                    self.flow[u][v] += d
                    self.flow[v][u] -= d
                    excess[u] -= d
                    excess[v] += d
                    if v != s and v != t and not in_queue[v] and excess[v] > 0:
                        active.append(v)
                        in_queue[v] = True
                    pushed = True
                    if excess[u] == 0:
                        break
            if not pushed:
                # Relabel
                min_height = float('inf')
                for v in range(n):
                    if self.cap[u][v] - self.flow[u][v] > 0:
                        min_height = min(min_height, height[v])
                height[u] = min_height + 1
 
        if excess[u] > 0 and not in_queue[u]:
            active.append(u)
            in_queue[u] = True
 
# 使用例
pr = PushRelabel(6)
pr.add_edge(0, 1, 10)
pr.add_edge(0, 2, 10)
pr.add_edge(1, 3, 4)
pr.add_edge(1, 4, 8)
pr.add_edge(2, 4, 9)
pr.add_edge(3, 5, 10)
pr.add_edge(4, 3, 6)
pr.add_edge(4, 5, 10)
print(pr.max_flow(0, 5))  # 19

adj = [
    [0, 1, 3],   # 学生0
    [1, 2],       # 学生1
    [0, 3],       # 学生2
    [2, 4],       # 学生3
    [1, 3, 4],    # 学生4
]
count, match_l, match_r = hopcroft_karp(5, 5, adj)
print(f"最大マッチング: {count}")  # 5（完全マッチング可能）
# 例: 学生0→研究室0, 学生1→研究室2, 学生2→研究室3,
#      学生3→研究室4, 学生4→研究室1

# 解法のスケルトン
mcf = MinCostFlow(2 + 3 + 4)  # s, t, 3工場, 4店舗
source, sink = 0, 1
factories = [2, 3, 4]      # ノード番号
stores = [5, 6, 7, 8]      # ノード番号
supply = [20, 30, 25]
demand = [15, 20, 25, 15]
cost_matrix = [
    [4, 6, 8, 5],
    [6, 3, 5, 7],
    [3, 8, 4, 6],
]
 
for i, f in enumerate(factories):
    mcf.add_edge(source, f, supply[i], 0)
 
for i, f in enumerate(factories):
    for j, s in enumerate(stores):
        mcf.add_edge(f, s, min(supply[i], demand[j]), cost_matrix[i][j])
 
for j, s in enumerate(stores):
    mcf.add_edge(s, sink, demand[j], 0)
 
total_demand = sum(demand)  # 75
flow, total_cost = mcf.min_cost_flow(source, sink, total_demand)
print(f"総輸送量: {flow}, 総コスト: {total_cost}")

# BAD: 最大流の値は求めたが、実際にどの辺にどれだけ流れたか不明
flow_value = dinic.max_flow(s, t)
# ここで「どの辺に何単位流れたか」を出力しようとしても
# 残余グラフから逆算する必要がある
 
# GOOD: フロー値と経路を同時に記録する設計
class DinicWithFlowRecovery(Dinic):
    def get_flow_on_edges(self):
        """各辺の実際のフロー量を復元"""
        result = []
        for u in range(self.n):
            for i, (v, cap, rev) in enumerate(self.graph[u]):
                # 元の辺（逆辺でない）のフロー量
                if i % 2 == 0:  # add_edge で追加された順辺
                    original_cap = cap + self.graph[v][rev][1]
                    flow = self.graph[v][rev][1]
                    if flow > 0:
                        result.append((u, v, flow, original_cap))
        return result

# BAD: 隣接行列で多重辺を上書き
cap[u][v] = 5   # 1本目
cap[u][v] = 3   # 2本目 → 上書き! 合計8ではなく3になる
 
# GOOD: 容量を加算する
cap[u][v] += 5   # 1本目
cap[u][v] += 3   # 2本目 → 合計8
 
# Dinic の隣接リスト版では自動的に別の辺として追加されるので
# この問題は発生しない（隣接行列版のみ注意）