# 問題理解のチェックリスト（実装前に必ず確認）
 
class ProblemUnderstanding:
    """問題を理解するためのフレームワーク"""
 
    def __init__(self, problem_text: str):
        self.problem_text = problem_text
        self.input_format = None    # 入力形式
        self.output_format = None   # 出力形式
        self.constraints = {}       # 制約条件
        self.edge_cases = []        # エッジケース
        self.examples = []          # 具体例
 
    def parse_constraints(self):
        """制約条件を構造化して抽出する"""
        # 典型的な制約パターン
        constraint_patterns = {
            'n_range': '1 <= n <= ?',
            'value_range': '値の範囲',
            'time_limit': '実行時間制限（通常2秒）',
            'memory_limit': 'メモリ制限（通常256MB）',
            'special': 'MOD, 座標範囲, 文字種等',
        }
        return constraint_patterns
 
    def identify_edge_cases(self):
        """エッジケースを体系的に洗い出す"""
        common_edges = [
            "n = 0 (空入力)",
            "n = 1 (最小入力)",
            "n = 最大制約 (TLE/MLEの境界)",
            "全要素が同一値",
            "既にソート済み / 完全逆順",
            "負の値・ゼロを含む",
            "答えが存在しない場合",
            "答えが複数存在する場合",
        ]
        return common_edges
 
    def rephrase(self) -> str:
        """問題を自分の言葉で言い換える"""
        # 「〜を求めよ」→「〜を最小化/最大化する」→「〜の条件を満たすものを数える」
        # この言い換えが正しいか、サンプルで検証する
        pass

# ============================================================
# 例題: 配列から和が target となるペアを見つける
# 制約: 1 <= n <= 10^5, -10^9 <= arr[i] <= 10^9
# ============================================================
 
# 制約分析:
# n = 10^5 → O(n^2) = 10^10 → TLE（タイムオーバー）
# → O(n log n) か O(n) が必要
# → 候補: ソート+二分探索、ソート+尺取り、ハッシュマップ
 
# === 解法1: O(n^2) 全ペア列挙（TLEだが正解確認用） ===
def two_sum_brute(arr: list[int], target: int) -> tuple[int, int] | None:
    """愚直解: 全ペアを列挙する O(n^2)"""
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == target:
                return (i, j)
    return None
 
# === 解法2: O(n log n) ソート + 二分探索 ===
def two_sum_sort(arr: list[int], target: int) -> tuple[int, int] | None:
    """ソート+尺取り法 O(n log n)"""
    indexed = sorted(enumerate(arr), key=lambda x: x[1])
    left, right = 0, len(arr) - 1
 
    while left < right:
        current_sum = indexed[left][1] + indexed[right][1]
        if current_sum == target:
            return (indexed[left][0], indexed[right][0])
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None
 
# === 解法3: O(n) ハッシュマップ（最適解） ===
def two_sum_hash(arr: list[int], target: int) -> tuple[int, int] | None:
    """ハッシュマップ O(n)"""
    seen: dict[int, int] = {}
    for i, num in enumerate(arr):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None
 
# === ストレステストで3解法を比較 ===
import random
 
def stress_test_two_sum(n_tests: int = 1000, max_n: int = 100):
    """ランダムテストで3つの解法を比較検証"""
    for test_id in range(n_tests):
        n = random.randint(2, max_n)
        arr = [random.randint(-100, 100) for _ in range(n)]
        target = random.randint(-200, 200)
 
        result_brute = two_sum_brute(arr, target)
        result_sort = two_sum_sort(arr, target)
        result_hash = two_sum_hash(arr, target)
 
        # 存在性の一致を確認
        has_brute = result_brute is not None
        has_sort = result_sort is not None
        has_hash = result_hash is not None
 
        assert has_brute == has_sort == has_hash, (
            f"Test {test_id}: 不一致! arr={arr}, target={target}"
        )
 
        # 解が存在する場合、正しいペアか確認
        if has_brute:
            i, j = result_hash
            assert arr[i] + arr[j] == target, (
                f"Test {test_id}: ハッシュ解が不正"
            )
    print(f"全{n_tests}テスト通過")
 
# stress_test_two_sum()  # 実行して検証

def classify_problem(problem_features: dict) -> list[str]:
    """
    問題の特徴からアルゴリズム候補を推定する
 
    problem_features の例:
    {
        'optimization': True,          # 最適化問題か
        'counting': False,             # 数え上げ問題か
        'decision': False,             # 判定問題か
        'graph': True,                 # グラフが関与するか
        'has_weights': True,           # 重み/コストがあるか
        'constraint_n': 100000,        # n の制約
        'overlapping_subproblems': True,  # 重複部分問題
        'greedy_choice': False,        # 貪欲選択性質
        'monotonic': True,             # 単調性があるか
    }
    """
    candidates = []
    n = problem_features.get('constraint_n', 0)
 
    # 最適化問題の分岐
    if problem_features.get('optimization'):
        if problem_features.get('greedy_choice'):
            candidates.append('貪欲法')
        if problem_features.get('overlapping_subproblems'):
            candidates.append('動的計画法')
        if problem_features.get('monotonic'):
            candidates.append('二分探索（答えの決め打ち）')
        if n <= 20:
            candidates.append('ビットDP / 全探索')
 
    # グラフ問題の分岐
    if problem_features.get('graph'):
        if problem_features.get('has_weights'):
            candidates.append('Dijkstra / Bellman-Ford')
        else:
            candidates.append('BFS / DFS')
 
    # 数え上げ問題
    if problem_features.get('counting'):
        candidates.append('DP')
        candidates.append('組合せ数学')
 
    # 判定問題
    if problem_features.get('decision'):
        if problem_features.get('monotonic'):
            candidates.append('二分探索')
 
    return candidates

# ============================================================
# パターン1: 固定長ウィンドウ
# ============================================================
def max_subarray_sum_k(arr: list[int], k: int) -> int:
    """長さ k の部分配列の最大和"""
    if len(arr) < k:
        return 0
 
    # 最初のウィンドウ
    window_sum = sum(arr[:k])
    max_sum = window_sum
 
    # ウィンドウをスライド
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]  # O(1) で更新
        max_sum = max(max_sum, window_sum)
 
    return max_sum
 
 
# ============================================================
# パターン2: 可変長ウィンドウ（条件を満たす最短区間）
# ============================================================
def min_subarray_len(arr: list[int], target: int) -> int:
    """和が target 以上となる最短の連続部分配列の長さ"""
    n = len(arr)
    min_len = float('inf')
    left = 0
    current_sum = 0
 
    for right in range(n):
        current_sum += arr[right]
 
        # 条件を満たす限り left を進める（区間を縮める）
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
 
    return min_len if min_len != float('inf') else 0
 
 
# ============================================================
# パターン3: 可変長ウィンドウ（条件を満たす最長区間）
# ============================================================
def longest_substring_k_distinct(s: str, k: int) -> int:
    """異なる文字が高々 k 種の最長部分文字列"""
    from collections import defaultdict
 
    char_count: dict[str, int] = defaultdict(int)
    left = 0
    max_len = 0
 
    for right in range(len(s)):
        char_count[s[right]] += 1
 
        # 条件を違反したら left を進める
        while len(char_count) > k:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1
 
        max_len = max(max_len, right - left + 1)
 
    return max_len
 
 
# ============================================================
# パターン4: 2つの配列に対する尺取り法（マージ操作）
# ============================================================
def merge_sorted_arrays(arr1: list[int], arr2: list[int]) -> list[int]:
    """ソート済み2配列のマージ O(n + m)"""
    result = []
    i, j = 0, 0
 
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1
 
    # 残りを追加
    result.extend(arr1[i:])
    result.extend(arr2[j:])
    return result
 
 
# ============================================================
# テスト
# ============================================================
print(max_subarray_sum_k([1, 4, 2, 10, 23, 3, 1, 0, 20], 4))  # 39
print(min_subarray_len([2, 3, 1, 2, 4, 3], 7))                  # 2
print(longest_substring_k_distinct("eceba", 2))                  # 3 ("ece")
print(merge_sorted_arrays([1, 3, 5], [2, 4, 6]))                # [1,2,3,4,5,6]

# ============================================================
# 例題1: 配列を k 分割したとき、各区間の和の最大値を最小化する
# (Painter's Partition Problem / Split Array Largest Sum)
# ============================================================
 
def min_max_partition(arr: list[int], k: int) -> int:
    """配列を k 分割したとき、各区間の和の最大値を最小化する"""
 
    def can_partition(max_sum: int) -> bool:
        """各区間の和が max_sum 以下で k 分割可能か？"""
        count = 1       # 現在の分割数
        current_sum = 0
        for num in arr:
            if current_sum + num > max_sum:
                count += 1
                current_sum = num
                if count > k:
                    return False
            else:
                current_sum += num
        return True
 
    # 答えの二分探索
    lo = max(arr)      # 最小: 最大要素1つだけの区間
    hi = sum(arr)      # 最大: 全体が1区間
    result = hi
 
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_partition(mid):
            result = mid
            hi = mid - 1   # より小さい答えを探す
        else:
            lo = mid + 1   # 答えを大きくする
 
    return result
 
 
# ============================================================
# 例題2: n 本の木から長さ L の丸太を k 本切り出す。L の最大値は？
# ============================================================
 
def max_log_length(trees: list[int], k: int) -> int:
    """n 本の木から長さ L の丸太を k 本以上切り出せる最大の L"""
 
    def count_logs(length: int) -> int:
        """長さ length で切り出せる丸太の本数"""
        return sum(t // length for t in trees)
 
    lo, hi = 1, max(trees)
    result = 0
 
    while lo <= hi:
        mid = (lo + hi) // 2
        if count_logs(mid) >= k:
            result = mid
            lo = mid + 1    # より大きな L を探す
        else:
            hi = mid - 1
 
    return result
 
 
# ============================================================
# 例題3: 実数値の二分探索（精度指定）
# ============================================================
 
def sqrt_binary_search(x: float, eps: float = 1e-9) -> float:
    """x の平方根を二分探索で求める"""
    lo, hi = 0.0, max(1.0, x)
 
    while hi - lo > eps:
        mid = (lo + hi) / 2
        if mid * mid <= x:
            lo = mid
        else:
            hi = mid
 
    return lo
 
 
# テスト
print(min_max_partition([7, 2, 5, 10, 8], 2))   # 18 ([7,2,5] と [10,8])
print(max_log_length([10, 24, 15], 7))           # 6
print(f"{sqrt_binary_search(2):.10f}")           # 1.4142135624

# ============================================================
# 1次元累積和
# ============================================================
def prefix_sum_queries(arr: list[int], queries: list[tuple[int, int]]) -> list[int]:
    """複数の区間和クエリを O(1) で回答"""
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
 
    results = []
    for l, r in queries:
        results.append(prefix[r + 1] - prefix[l])
 
    return results
 
 
# ============================================================
# 2次元累積和
# ============================================================
def build_prefix_sum_2d(matrix: list[list[int]]) -> list[list[int]]:
    """2次元累積和の構築 O(rows * cols)"""
    if not matrix or not matrix[0]:
 
    rows, cols = len(matrix), len(matrix[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
 
    for i in range(rows):
        for j in range(cols):
            prefix[i + 1][j + 1] = (
                matrix[i][j]
                + prefix[i][j + 1]
                + prefix[i + 1][j]
                - prefix[i][j]         # 包除原理
            )
 
    return prefix
 
 
def query_2d(prefix: list[list[int]], r1: int, c1: int, r2: int, c2: int) -> int:
    """(r1,c1)-(r2,c2) の矩形和 O(1)"""
    return (
        prefix[r2 + 1][c2 + 1]
        - prefix[r1][c2 + 1]
        - prefix[r2 + 1][c1]
        + prefix[r1][c1]              # 包除原理
    )
 
 
# ============================================================
# 累積和の応用: いもす法（差分配列）
# ============================================================
def range_add_queries(n: int, queries: list[tuple[int, int, int]]) -> list[int]:
    """
    いもす法: 区間加算クエリを効率的に処理する
    queries: [(l, r, val), ...] → arr[l..r] に val を加算
    全クエリ処理後の配列を返す
 
    計算量: O(n + Q)  （Q = クエリ数）
    """
    diff = [0] * (n + 1)   # 差分配列
 
    for l, r, val in queries:
        diff[l] += val
        if r + 1 < n:
            diff[r + 1] -= val
 
    # 差分配列の累積和 = 最終的な配列
    result = [0] * n
    result[0] = diff[0]
    for i in range(1, n):
        result[i] = result[i - 1] + diff[i]
 
    return result
 
 
# テスト
arr = [3, 1, 4, 1, 5, 9, 2, 6]
print(prefix_sum_queries(arr, [(0, 3), (2, 5), (0, 7)]))
# [9, 19, 31]
 
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
prefix = build_prefix_sum_2d(matrix)
print(query_2d(prefix, 0, 0, 1, 1))  # 1+2+4+5 = 12
print(query_2d(prefix, 1, 1, 2, 2))  # 5+6+8+9 = 28
 
print(range_add_queries(5, [(1, 3, 2), (0, 2, 1), (2, 4, 3)]))
# [1, 3, 6, 5, 3]

# ============================================================
# パターン1: 1次元DP（最長増加部分列 LIS）
# ============================================================
import bisect
 
def lis_length(arr: list[int]) -> int:
    """最長増加部分列の長さ O(n log n)"""
    # tails[i] = 長さ (i+1) の増加部分列の末尾要素の最小値
    tails: list[int] = []
 
    for num in arr:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)   # 新しい長さの部分列
        else:
            tails[pos] = num    # より小さい末尾に更新
 
    return len(tails)
 
 
# ============================================================
# パターン2: 2次元DP（ナップサック問題）
# ============================================================
def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    """0-1 ナップサック問題 O(n * capacity)"""
    n = len(weights)
    # dp[j] = 容量 j で得られる最大価値（1次元に圧縮）
    dp = [0] * (capacity + 1)
 
    for i in range(n):
        # 逆順にループ（各品物を1回だけ使うため）
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
 
    return dp[capacity]
 
 
# ============================================================
# パターン3: 区間DP（行列連鎖乗算）
# ============================================================
def matrix_chain_order(dims: list[int]) -> int:
    """
    行列連鎖乗算の最小コスト O(n^3)
    dims[i-1] x dims[i] が i 番目の行列のサイズ
    """
    n = len(dims) - 1  # 行列の数
    # dp[i][j] = 行列 i..j を掛け合わせる最小コスト
    dp = [[0] * n for _ in range(n)]
 
    # 区間の長さを 2 から n まで増やす
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                dp[i][j] = min(dp[i][j], cost)
 
    return dp[0][n - 1]
 
 
# ============================================================
# パターン4: ビットDP（巡回セールスマン問題 TSP）
# ============================================================
def tsp(dist: list[list[int]]) -> int:
    """
    巡回セールスマン問題 O(2^n * n^2)
    dist[i][j] = 都市 i から j への距離
    """
    n = len(dist)
    INF = float('inf')
    # dp[S][i] = 集合 S の都市を訪問済みで、現在都市 i にいる最小コスト
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 都市0からスタート
 
    for S in range(1 << n):
        for u in range(n):
            if dp[S][u] == INF:
                continue
            if not (S >> u & 1):
                continue
            for v in range(n):
                if S >> v & 1:
                    continue  # 既に訪問済み
                new_S = S | (1 << v)
                dp[new_S][v] = min(dp[new_S][v], dp[S][u] + dist[u][v])
 
    # 全都市を訪問して都市0に戻る
    full = (1 << n) - 1
    return min(dp[full][i] + dist[i][0] for i in range(n))
 
 
# テスト
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))  # 4 ([2,3,7,101] or [2,5,7,101])
print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))    # 10
print(matrix_chain_order([10, 30, 5, 60]))         # 4500
 
dist_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
print(tsp(dist_matrix))  # 80 (0→1→3→2→0)

import math
import random
 
def dist(p1: tuple[float, float], p2: tuple[float, float]) -> float:
    """2点間のユークリッド距離"""
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
 
 
# === 段階1: O(n^2) 愚直解 ===
def closest_pair_brute(points: list[tuple[float, float]]) -> float:
    """全ペアの距離を計算"""
    n = len(points)
    min_dist = float('inf')
    for i in range(n):
        for j in range(i + 1, n):
            d = dist(points[i], points[j])
            min_dist = min(min_dist, d)
    return min_dist
 
 
# === 段階2: ソート + 枝刈り ===
def closest_pair_sorted(points: list[tuple[float, float]]) -> float:
    """x座標でソートし、距離が min_dist 以上なら枝刈り"""
    points_sorted = sorted(points)  # x座標でソート
    n = len(points_sorted)
    min_dist = float('inf')
 
    for i in range(n):
        for j in range(i + 1, n):
            # x座標の差だけで min_dist 以上なら、以降は全てスキップ
            if points_sorted[j][0] - points_sorted[i][0] >= min_dist:
                break
            d = dist(points_sorted[i], points_sorted[j])
            min_dist = min(min_dist, d)
 
    return min_dist
 
 
# === 段階3: 分割統治 O(n log n) ===
def closest_pair_dnc(points: list[tuple[float, float]]) -> float:
    """分割統治法による最近接点対"""
    def solve(pts_x: list, pts_y: list) -> float:
        n = len(pts_x)
        if n <= 3:
            return closest_pair_brute(pts_x)
 
        mid = n // 2
        mid_x = pts_x[mid][0]
 
        # 左右に分割
        left_x = pts_x[:mid]
        right_x = pts_x[mid:]
        left_set = set(map(id, left_x))
 
        left_y = [p for p in pts_y if id(p) in left_set]  # 簡易実装
        right_y = [p for p in pts_y if id(p) not in left_set]
 
        d_left = solve(left_x, left_y)
        d_right = solve(right_x, right_y)
        d = min(d_left, d_right)
 
        # ストリップ内の点を確認
        strip = [p for p in pts_y if abs(p[0] - mid_x) < d]
 
        for i in range(len(strip)):
            j = i + 1
            while j < len(strip) and strip[j][1] - strip[i][1] < d:
                d = min(d, dist(strip[i], strip[j]))
                j += 1
 
        return d
 
    pts_x = sorted(points, key=lambda p: p[0])
    pts_y = sorted(points, key=lambda p: p[1])
    return solve(pts_x, pts_y)
 
 
# === ストレステスト ===
def stress_test_closest_pair(n_tests: int = 200):
    """愚直解と最適解を比較するストレステスト"""
    for test_id in range(n_tests):
        n = random.randint(2, 50)
        points = [(random.uniform(-100, 100), random.uniform(-100, 100))
                   for _ in range(n)]
 
        d_brute = closest_pair_brute(points)
        d_sorted = closest_pair_sorted(points)
        d_dnc = closest_pair_dnc(points)
 
        assert abs(d_brute - d_sorted) < 1e-9, f"Test {test_id}: sorted 不一致"
        assert abs(d_brute - d_dnc) < 1e-9, f"Test {test_id}: dnc 不一致"
 
    print(f"全{n_tests}テスト通過")
 
# stress_test_closest_pair()

import random
import time
 
def stress_test(brute_fn, optimized_fn, generator_fn,
                comparator=None, n_tests: int = 1000, verbose: bool = False):
    """
    汎用ストレステストフレームワーク
 
    brute_fn:      愚直解（正しい答えを返す関数）
    optimized_fn:  最適化解（テスト対象の関数）
    generator_fn:  テスト入力を生成する関数
    comparator:    結果の比較関数（None ならば == で比較）
    """
    compare = comparator or (lambda a, b: a == b)
 
    for test_id in range(n_tests):
        test_input = generator_fn()
        # 同じ入力に対する結果を比較
        result_brute = brute_fn(*test_input)
        result_opt = optimized_fn(*test_input)
 
        if not compare(result_brute, result_opt):
            print(f"不一致! テスト #{test_id}")
            print(f"  入力:     {test_input}")
            print(f"  愚直解:   {result_brute}")
            print(f"  最適化解: {result_opt}")
            return False
 
        if verbose and test_id % 100 == 0:
            print(f"  テスト #{test_id} 通過")
 
    print(f"全{n_tests}テスト通過")
    return True
 
 
# 使用例
def gen_two_sum_input():
    n = random.randint(2, 100)
    arr = [random.randint(-100, 100) for _ in range(n)]
    target = random.randint(-200, 200)
    return (arr, target)
 
# stress_test(two_sum_brute, two_sum_hash, gen_two_sum_input, n_tests=5000)

# ================================================================
# BAD: n=10^5 なのに O(n^2) を実装
# → 10^10 回の演算 → TLE（制限時間超過）
# ================================================================
 
def find_duplicate_bad(arr: list[int]) -> int:
    """O(n^2): 全ペアを比較して重複を探す"""
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return arr[i]
    return -1
 
# ================================================================
# GOOD: 制約を先に確認し、許容される計算量を見積もる
# n=10^5 → O(n log n) 以下が必要
# ================================================================
 
def find_duplicate_good(arr: list[int]) -> int:
    """O(n): ハッシュセットで重複を検出"""
    seen: set[int] = set()
    for num in arr:
        if num in seen:
            return num
        seen.add(num)
    return -1

# ================================================================
# BAD: 最初から複雑な最適アルゴリズムを実装しようとする
# → バグが入りやすい、デバッグが困難、時間を浪費
# ================================================================
 
# いきなりセグメント木 + 座標圧縮 + オフラインクエリを書き始める...
 
# ================================================================
# GOOD: まず愚直解を実装し、正しい出力を確認してから最適化
# ================================================================
 
# Step 1: O(n^2) の愚直解で正解を確認
# Step 2: O(n log n) の最適解を実装
# Step 3: ストレステストで愚直解と最適解を比較してバグを検出
# Step 4: 大きな入力での実行時間を確認

# ================================================================
# BAD: グローバル変数を多用し、状態管理が混乱
# ================================================================
 
visited = set()       # グローバル → テストケース間で初期化忘れ
result = []           # グローバル → 複数回呼び出しで汚染
 
def dfs_bad(graph, v):
    visited.add(v)
    for u in graph[v]:
        if u not in visited:
            dfs_bad(graph, u)
 
# ================================================================
# GOOD: 状態を引数や返り値で管理、または関数内にカプセル化
# ================================================================
 
def dfs_good(graph: dict, start: int) -> set[int]:
    """状態を関数内にカプセル化"""
    visited: set[int] = set()
    stack = [start]
 
    while stack:
        v = stack.pop()
        if v in visited:
            continue
        visited.add(v)
        for u in graph[v]:
            if u not in visited:
                stack.append(u)
 
    return visited

# ================================================================
# BAD: 浮動小数点数を == で比較
# ================================================================
 
def is_right_triangle_bad(a: float, b: float, c: float) -> bool:
    return a*a + b*b == c*c  # 浮動小数点誤差で False になる可能性
 
# ================================================================
# GOOD: 誤差を考慮した比較
# ================================================================
 
EPS = 1e-9
 
def is_right_triangle_good(a: float, b: float, c: float) -> bool:
    return abs(a*a + b*b - c*c) < EPS

# ================================================================
# BAD: Python のデフォルト再帰上限（1000）を超える
# ================================================================
 
def dfs_recursive_bad(graph, v, visited):
    visited.add(v)
    for u in graph[v]:
        if u not in visited:
            dfs_recursive_bad(graph, u, visited)
    # n=10000 の線形グラフで RecursionError
 
# ================================================================
# GOOD: 再帰上限を引き上げるか、スタックで実装
# ================================================================
 
import sys
sys.setrecursionlimit(300000)  # 再帰上限を引き上げ
 
# または、スタックベースの反復実装（推奨）
def dfs_iterative(graph: dict, start: int) -> list[int]:
    visited = set()
    stack = [start]
    order = []
 
    while stack:
        v = stack.pop()
        if v in visited:
            continue
        visited.add(v)
        order.append(v)
        for u in reversed(graph[v]):
            if u not in visited:
                stack.append(u)
 
    return order