F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int prev2 = 0; // F(i-2)
        int prev1 = 1; // F(i-1)
        for (int i = 2; i <= n; i++) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1; // F(n)
    }
}

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int prev1 = 1; // 到第 i-2 阶的方法数
        int prev2 = 2; // 到第 i-1 阶的方法数
        for (int i = 3; i <= n; i++) {
            int cur = prev2 + prev1;
            prev1 = prev2;
            prev2 = cur;
        }
        return prev2;
    }
}

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev2 = cost[0]; // 到达 i-2 并付费的最低花费
        int prev1 = cost[1]; // 到达 i-1 并付费的最低花费
        for (int i = 2; i < n; i++) {
            int cur = cost[i] + Math.min(prev2, prev1);
            prev2 = prev1;
            prev1 = cur;
        }
        // 可从最后一阶或倒数第二阶迈向楼顶，无需再付楼顶费用
        return Math.min(prev2, prev1);
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        // C(m+n-2, m-1)，边乘边除保证整除、控制溢出
        long ans = 1;
        int a = m - 1;
        int b = n - 1;
        if (a > b) { // 取较小者为循环次数
            int t = a;
            a = b;
            b = t;
        }
        for (int i = 1; i <= a; i++) {
            ans = ans * (b + i) / i;
        }
        return (int) ans;
    }
}

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) {
            return 0; // 起点被堵
        }
        int[] dp = new int[n]; // dp[j]：到当前行第 j 列的路径数
        dp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0; // 障碍：不可达
                    continue;
                }
                if (j > 0) {
                    dp[j] += dp[j - 1]; // 从左边来；dp[j] 原值是从上边滚下来的
                }
            }
        }
        return dp[n - 1];
    }
}

class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1; // 2→1+1；3→1+2
        }
        int ans = 1;
        // 尽量拆出 3；剩下 4 时拆成 2+2（因为 3+1 更差）
        while (n > 4) {
            ans *= 3;
            n -= 3;
        }
        ans *= n; // 剩余 2、3 或 4
        return ans;
    }
}

class Solution {
    public int numTrees(int n) {
        // 卡特兰数：C_0=1，C_{i+1} = C_i * 2(2i+1)/(i+2)
        long ans = 1;
        for (int i = 0; i < n; i++) {
            ans = ans * 2 * (2L * i + 1) / (i + 2);
        }
        return (int) ans;
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        if (total % 2 != 0) {
            return false; // 奇数无法平分
        }
        int target = total / 2;
        boolean[] dp = new boolean[target + 1]; // dp[j]：能否凑出和 j
        dp[0] = true;
        for (int num : nums) {
            // 倒序：保证每个 num 在本轮只被用一次
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
}

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int target = sum / 2; // 一堆尽量靠近 sum/2
        boolean[] dp = new boolean[target + 1]; // dp[j]：能否凑出重量 j
        dp[0] = true;
        for (int stone : stones) {
            // 01 背包：倒序，每块石头只用一次
            for (int j = target; j >= stone; j--) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }
        // 找最大的可凑 j，剩余重量 = sum - 2j
        for (int j = target; j >= 0; j--) {
            if (dp[j]) {
                int ans = sum - 2 * j;
                return ans;
            }
        }
        return 0;
    }
}

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // P = (sum + target) / 2，无法整除或越界则无解
        if ((sum + target) % 2 != 0 || Math.abs(target) > sum) {
            return 0;
        }
        int pack = (sum + target) / 2;
        int[] dp = new int[pack + 1]; // dp[j]：凑出 j 的方案数
        dp[0] = 1;
        for (int num : nums) {
            // 01 背包倒序：每个数只用一次
            for (int j = pack; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        int ans = dp[pack];
        return ans;
    }
}

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        // dp[i][j]：最多 i 个 0、j 个 1 时的最大子集长度
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int zeros = 0;
            int ones = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    zeros++;
                } else {
                    ones++;
                }
            }
            // 01 背包：两维均倒序，保证每个字符串只用一次
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }
        int ans = dp[m][n];
        return ans;
    }
}

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1]; // dp[j]：凑出 j 的组合数
        dp[0] = 1; // 凑出 0 只有一种：什么都不选
        // 外层硬币：每种币可重复用，且顺序无关 → 组合
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin]; // 用当前币凑 j
            }
        }
        int ans = dp[amount];
        return ans;
    }
}

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1]; // dp[i]：凑出 i 的排列数
        dp[0] = 1; // 空排列
        // 外层容量：保证考虑顺序
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num]; // 末尾接上 num
                }
            }
        }
        int ans = dp[target];
        return ans;
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1]; // dp[j]：凑出 j 的最少硬币数
        Arrays.fill(dp, amount + 1); // 不可能达到的大值
        dp[0] = 0;
        for (int coin : coins) {
            // 正序：同一硬币可多次使用
            for (int j = coin; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1]; // dp[i]：和为 i 的最少个数
        Arrays.fill(dp, n + 1); // 足够大的初值
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> dict = new HashSet<>(wordDict); // 判断子串是否在字典中
        int maxLen = 0;
        for (String word : wordDict) {
            maxLen = Math.max(maxLen, word.length());
        }
        boolean[] dp = new boolean[n + 1]; // dp[i]：前 i 个字符能否拆出
        dp[0] = true; // 空串可拆
        for (int i = 1; i <= n; i++) {
            // 只枚举长度 ≤ 最长单词的切分点
            int start = Math.max(0, i - maxLen);
            for (int j = i - 1; j >= start; j--) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // 能拆即可，不必再试别的 j
                }
            }
        }
        boolean ans = dp[n];
        return ans;
    }
}

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        // prev1：偷到 i-2 的最高金额；prev2：偷到 i-1 的最高金额
        int prev1 = nums[0];
        int prev2 = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            // 不偷 i 用 prev2；偷 i 则加上 prev1
            int curr = Math.max(prev2, prev1 + nums[i]);
            prev1 = prev2;
            prev2 = curr;
        }
        int ans = prev2;
        return ans;
    }
}

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        // 不偷最后一家 / 不偷第一家，取更优
        int ans = Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
        return ans;
    }

    // 在闭区间 [left, right] 上做线性打家劫舍
    private int robRange(int[] nums, int left, int right) {
        int prev1 = 0; // 到 i-2 的最优
        int prev2 = 0; // 到 i-1 的最优
        for (int i = left; i <= right; i++) {
            int curr = Math.max(prev2, prev1 + nums[i]);
            prev1 = prev2;
            prev2 = curr;
        }
        return prev2;
    }
}

class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root); // res[0] 不偷根；res[1] 偷根
        int ans = Math.max(res[0], res[1]);
        return ans;
    }

    // 返回 {不偷当前, 偷当前} 时该子树能得到的最大金额
    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[] { 0, 0 };
        }
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        // 不偷当前：左右可选偷或不偷
        int skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        // 偷当前：左右都不能偷
        int take = node.val + left[0] + right[0];
        return new int[] { skip, take };
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = prices[0]; // 迄今最低买入价
        int ans = 0;
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price; // 更低的买入点
            } else {
                // 今天卖出相对历史最低的利润
                ans = Math.max(ans, price - minPrice);
            }
        }
        return ans;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        // buy1/sell1：完成至多 1 笔；buy2/sell2：完成至多 2 笔
        int buy1 = Integer.MIN_VALUE / 2; // 持有第 1 股时的最大利润（可为负）
        int sell1 = 0;
        int buy2 = Integer.MIN_VALUE / 2;
        int sell2 = 0;
        for (int price : prices) {
            buy1 = Math.max(buy1, -price);           // 第一次买入
            sell1 = Math.max(sell1, buy1 + price);   // 第一次卖出
            buy2 = Math.max(buy2, sell1 - price);    // 第二次买入（用 sell1 的现金）
            sell2 = Math.max(sell2, buy2 + price);   // 第二次卖出
        }
        int ans = sell2; // 至多两笔，最终一定不持仓更优
        return ans;
    }
}

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }
        // 交易次数足够多：等价无限次买卖
        if (k >= n / 2) {
            int ans = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    ans += prices[i] - prices[i - 1];
                }
            }
            return ans;
        }
        int[] buy = new int[k + 1];  // buy[j]：第 j 笔买入后持仓
        int[] sell = new int[k + 1]; // sell[j]：第 j 笔卖出后空仓
        Arrays.fill(buy, Integer.MIN_VALUE / 2);
        for (int price : prices) {
            for (int j = 1; j <= k; j++) {
                buy[j] = Math.max(buy[j], sell[j - 1] - price);
                sell[j] = Math.max(sell[j], buy[j] + price);
            }
        }
        int ans = sell[k];
        return ans;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int hold = Integer.MIN_VALUE / 2; // 持仓
        int sold = 0; // 今日卖出 → 明日冷冻
        int rest = 0; // 空仓且可买
        for (int price : prices) {
            int prevHold = hold;
            int prevSold = sold;
            int prevRest = rest;
            hold = Math.max(prevHold, prevRest - price); // 继续持 / 今日买
            sold = prevHold + price;                     // 今日卖出
            rest = Math.max(prevRest, prevSold);         // 继续空仓 / 冷冻结束
        }
        int ans = Math.max(sold, rest); // 结束时不应持仓
        return ans;
    }
}

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int hold = Integer.MIN_VALUE / 2; // 持仓时的最大利润
        int cash = 0; // 空仓时的最大利润
        for (int price : prices) {
            int prevHold = hold;
            int prevCash = cash;
            hold = Math.max(prevHold, prevCash - price);           // 买入
            cash = Math.max(prevCash, prevHold + price - fee);     // 卖出并扣手续费
        }
        int ans = cash;
        return ans;
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
        // tails[k]：长度为 k+1 的递增子序列中，结尾的最小值
        int[] tails = new int[nums.length];
        int size = 0; // tails 当前有效长度 = 当前 LIS 长度
        for (int num : nums) {
            int left = 0;
            int right = size;
            // 下界：第一个 >= num 的下标
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tails[left] = num; // 用更小的结尾替换，或接到末尾
            if (left == size) {
                size++; // 扩展了最长长度
            }
        }
        int ans = size;
        return ans;
    }
}

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 1;
        int left = 0; // 当前连续递增段起点
        for (int right = 1; right < nums.length; right++) {
            if (nums[right] <= nums[right - 1]) {
                // 断掉：结算 [left, right) 并开新段
                ans = Math.max(ans, right - left);
                left = right;
            }
        }
        // 最后一段可能一直递增到末尾
        ans = Math.max(ans, nums.length - left);
        return ans;
    }
}

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // dp[i][j]：以 nums1[i-1]、nums2[j-1] 结尾的最长公共子数组长度
        int[][] dp = new int[m + 1][n + 1];
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ans = Math.max(ans, dp[i][j]);
                }
                // 不等则保持 0：公共子数组在此处断开
            }
        }
        return ans;
    }
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        // dp[i][j]：text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // 两端字符可同时选入公共子序列
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 至少丢掉其中一个串的当前字符
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        int ans = dp[m][n];
        return ans;
    }
}

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // dp[i][j]：nums1[0..i) 与 nums2[0..j) 的 LCS 长度
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1; // 连一条线
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        int ans = dp[m][n];
        return ans;
    }
}

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0; // s 的匹配进度
        int j = 0; // t 的扫描下标
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++; // 匹配到 s 的下一字符
            }
            j++;
        }
        boolean ans = i == s.length(); // s 全部匹配完
        return ans;
    }
}

// 进阶写法（与上题双指针二选一）
int n = t.length();
int[][] nxt = new int[n + 1][26];
Arrays.fill(nxt[n], n);
for (int i = n - 1; i >= 0; i--) {
    nxt[i] = nxt[i + 1].clone();
    nxt[i][t.charAt(i) - 'a'] = i;
}
int i = -1;
for (char c : s.toCharArray()) {
    i = nxt[i + 1][c - 'a'];
    if (i == n) {
        return false;
    }
}
return true;

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        // dp[i][j]：s[0..i) 的子序列中等于 t[0..j) 的个数
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1; // 构成空串只有 1 种：全删
        }
        for (int j = 1; j <= n; j++) {
            // i 从 j 起：s 长度不足 j 时不可能构成 t 前 j 个
            for (int i = j; i <= m; i++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // 用 s[i-1] 匹配 t[j-1] + 不用 s[i-1]
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j]; // 只能跳过 s[i-1]
                }
            }
        }
        int ans = dp[m][n];
        return ans;
    }
}

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        // dp[i][j]：word1[0..i) 与 word2[0..j) 的 LCS 长度
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        int ans = m + n - 2 * dp[m][n]; // 两边非 LCS 字符都删掉
        return ans;
    }
}

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        // dp[i][j]：word1[0..i) → word2[0..j) 的最少操作数
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // 删掉 word1 前 i 个字符
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // 插入 word2 前 j 个字符
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; // 无需操作
                } else {
                    // 删 word1[i-1] / 在 word1 插入 word2[j-1] / 替换
                    dp[i][j] = Math.min(
                            Math.min(dp[i - 1][j], dp[i][j - 1]),
                            dp[i - 1][j - 1]) + 1;
                }
            }
        }
        int ans = dp[m][n];
        return ans;
    }
}

class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            ans += expand(s, i, i);     // 奇数长度：中心 s[i]
            ans += expand(s, i, i + 1); // 偶数长度：中心在 s[i] 与 s[i+1] 之间
        }
        return ans;
    }

    // 从 [left, right] 向两边扩展，返回以该中心得到的回文个数
    private int expand(String s, int left, int right) {
        int count = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
        return count;
    }
}

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n]; // dp[i][j]：s[i..j] 是否回文
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) { // i 倒序：先算更短的内侧
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    // 长度 1～2 直接回文；更长则看去掉两端后是否回文
                    if (j - i <= 1 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        // dp[l][r]：s[l..r] 的最长回文子序列长度
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1; // 单字符
        }
        // 右端点 r 增大；左端点 l 从 r 往左扫，保证依赖已算
        for (int r = 1; r < n; r++) {
            for (int l = r - 1; l >= 0; l--) {
                if (s.charAt(l) == s.charAt(r)) {
                    // 长度 2：中间为空，结果为 2；更长则夹住内侧
                    dp[l][r] = (r - l == 1) ? 2 : dp[l + 1][r - 1] + 2;
                } else {
                    dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
                }
            }
        }
        int ans = dp[0][n - 1];
        return ans;
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n]; // 默认 0：后面没有更高
        Deque<Integer> stack = new ArrayDeque<>(); // 存下标，对应温度单调不增
        for (int i = 0; i < n; i++) {
            // 今天比栈顶更热：结算栈顶那天
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int j = stack.pop();
                ans[j] = i - j; // 要等的天数
            }
            stack.push(i); // 今天尚未找到更热天，入栈
        }
        return ans;
    }
}

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>(); // 值 → 右侧下一个更大
        Deque<Integer> stack = new ArrayDeque<>(); // 存 nums2 的值，单调不增
        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                nextGreater.put(stack.pop(), num); // 栈顶的下一个更大就是 num
            }
            stack.push(num);
        }
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = nextGreater.getOrDefault(nums1[i], -1);
        }
        return ans;
    }
}

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1); // 默认没有下一个更大
        Deque<Integer> stack = new ArrayDeque<>(); // 存下标，对应值单调不增
        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;
            while (!stack.isEmpty() && nums[stack.peek()] < nums[idx]) {
                ans[stack.pop()] = nums[idx];
            }
            // 第一圈入栈等待；第二圈只负责结算，避免重复压入同一下标
            if (i < n) {
                stack.push(idx);
            }
        }
        return ans;
    }
}

class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxLeft = 0;  // 已扫过的左侧最高
        int maxRight = 0; // 已扫过的右侧最高
        int ans = 0;
        while (left < right) {
            // 较矮一侧决定水位上界
            if (height[left] <= height[right]) {
                maxLeft = Math.max(maxLeft, height[left]);
                ans += maxLeft - height[left];
                left++;
            } else {
                maxRight = Math.max(maxRight, height[right]);
                ans += maxRight - height[right];
                right--;
            }
        }
        return ans;
    }
}

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // 左右哨兵高度 0：保证栈底安全，并在结尾强制弹空
        int[] h = new int[n + 2];
        System.arraycopy(heights, 0, h, 1, n);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0); // 左哨兵下标
        int ans = 0;
        for (int i = 1; i < n + 2; i++) {
            // 当前更矮：栈顶柱的右边界就是 i
            while (h[i] < h[stack.peek()]) {
                int height = h[stack.pop()];
                // 弹出后栈顶 = 左侧第一个更矮（或等矮）柱
                int width = i - stack.peek() - 1;
                ans = Math.max(ans, height * width);
            }
            stack.push(i);
        }
        return ans;
    }
}

import java.util.*;

public class Main {
    static List<List<Integer>> graph;
    static List<Integer> path;
    static List<List<Integer>> ans; // 所有 1→n 路径

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int s = in.nextInt();
            int t = in.nextInt();
            graph.get(s).add(t); // 有向边 s → t
        }

        path = new ArrayList<>();
        ans = new ArrayList<>();
        path.add(1);
        dfs(1, n);

        if (ans.isEmpty()) {
            System.out.println(-1);
        } else {
            for (List<Integer> p : ans) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < p.size(); i++) {
                    if (i > 0) {
                        sb.append(' ');
                    }
                    sb.append(p.get(i));
                }
                System.out.println(sb); // 行末无空格
            }
        }
        in.close();
    }

    static void dfs(int cur, int n) {
        if (cur == n) { // 到达终点，记录一条完整路径
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int nxt : graph.get(cur)) {
            path.add(nxt);
            dfs(nxt, n);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

import java.util.*;

public class Main {
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int n, m;
    static int[][] grid;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) { // 新岛屿
                    dfs(i, j);
                    ans++;
                }
            }
        }
        System.out.println(ans);
        in.close();
    }

    // 把 (i,j) 所在岛屿全部淹成 0，避免重复计数
    static void dfs(int i, int j) {
        grid[i][j] = 0;
        for (int[] d : dirs) {
            int x = i + d[0];
            int y = j + d[1];
            if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                dfs(x, y);
            }
        }
    }
}

import java.util.*;

public class Main {
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int n, m;
    static int[][] grid;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    ans = Math.max(ans, dfs(i, j));
                }
            }
        }
        System.out.println(ans);
        in.close();
    }

    // 返回从 (i,j) 出发淹没的陆地格数
    static int dfs(int i, int j) {
        grid[i][j] = 0;
        int area = 1;
        for (int[] d : dirs) {
            int x = i + d[0];
            int y = j + d[1];
            if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                area += dfs(x, y);
            }
        }
        return area;
    }
}

import java.util.*;

public class Main {
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int n, m;
    static int[][] grid;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        // 从四条边界把「非孤岛」淹没成 0
        for (int i = 0; i < n; i++) {
            if (grid[i][0] == 1) {
                dfs(i, 0);
            }
            if (grid[i][m - 1] == 1) {
                dfs(i, m - 1);
            }
        }
        for (int j = 0; j < m; j++) {
            if (grid[0][j] == 1) {
                dfs(0, j);
            }
            if (grid[n - 1][j] == 1) {
                dfs(n - 1, j);
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
        in.close();
    }

    static void dfs(int i, int j) {
        grid[i][j] = 0;
        for (int[] d : dirs) {
            int x = i + d[0];
            int y = j + d[1];
            if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                dfs(x, y);
            }
        }
    }
}

import java.util.*;

public class Main {
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int n, m;
    static int[][] grid;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        // 边界陆地标记为 2：这些岛不能沉
        for (int i = 0; i < n; i++) {
            if (grid[i][0] == 1) {
                dfs(i, 0);
            }
            if (grid[i][m - 1] == 1) {
                dfs(i, m - 1);
            }
        }
        for (int j = 0; j < m; j++) {
            if (grid[0][j] == 1) {
                dfs(0, j);
            }
            if (grid[n - 1][j] == 1) {
                dfs(n - 1, j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0; // 孤岛沉没
                } else if (grid[i][j] == 2) {
                    grid[i][j] = 1; // 靠边岛还原
                }
            }
        }

        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < m; j++) {
                sb.append(grid[i][j]).append(' '); // 题面要求每个元素后都有空格
            }
            System.out.println(sb);
        }
        in.close();
    }

    static void dfs(int i, int j) {
        grid[i][j] = 2;
        for (int[] d : dirs) {
            int x = i + d[0];
            int y = j + d[1];
            if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                dfs(x, y);
            }
        }
    }
}

import java.util.*;

public class Main {
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int n, m;
    static int[][] height;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        height = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                height[i][j] = in.nextInt();
            }
        }

        boolean[][] first = new boolean[n][m];  // 能流到第一组边界（左、上）
        boolean[][] second = new boolean[n][m]; // 能流到第二组边界（右、下）

        for (int i = 0; i < n; i++) {
            dfs(i, 0, first);
            dfs(i, m - 1, second);
        }
        for (int j = 0; j < m; j++) {
            dfs(0, j, first);
            dfs(n - 1, j, second);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (first[i][j] && second[i][j]) {
                    System.out.println(i + " " + j);
                }
            }
        }
        in.close();
    }

    // 反向：从边界往「高度不低于当前」的格子走
    static void dfs(int i, int j, boolean[][] vis) {
        vis[i][j] = true;
        for (int[] d : dirs) {
            int x = i + d[0];
            int y = j + d[1];
            if (x < 0 || x >= n || y < 0 || y >= m || vis[x][y]) {
                continue;
            }
            if (height[x][y] < height[i][j]) { // 反向不能走到更低
                continue;
            }
            dfs(x, y, vis);
        }
    }
}

import java.util.*;

public class Main {
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int n, m;
    static int[][] grid;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        // islandId 从 2 起，避免和 0/1 冲突；area[id] 为该岛面积
        int[] area = new int[n * m + 2];
        int id = 2;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    area[id] = dfs(i, j, id);
                    ans = Math.max(ans, area[id]); // 不填水时的最大岛
                    id++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] != 0) {
                    continue;
                }
                Set<Integer> neigh = new HashSet<>(); // 同一岛只加一次
                for (int[] d : dirs) {
                    int x = i + d[0];
                    int y = j + d[1];
                    if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] > 1) {
                        neigh.add(grid[x][y]);
                    }
                }
                int sum = 1; // 当前这格水变陆地
                for (int island : neigh) {
                    sum += area[island];
                }
                ans = Math.max(ans, sum);
            }
        }
        System.out.println(ans);
        in.close();
    }

    static int dfs(int i, int j, int id) {
        grid[i][j] = id;
        int cnt = 1;
        for (int[] d : dirs) {
            int x = i + d[0];
            int y = j + d[1];
            if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                cnt += dfs(x, y, id);
            }
        }
        return cnt;
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] grid = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = in.nextInt();
            }
        }

        int land = 0;
        int adj = 0; // 水平或垂直相邻的陆地对数
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    continue;
                }
                land++;
                if (j + 1 < m && grid[i][j + 1] == 1) {
                    adj++;
                }
                if (i + 1 < n && grid[i + 1][j] == 1) {
                    adj++;
                }
            }
        }
        int ans = 4 * land - 2 * adj;
        System.out.println(ans);
        in.close();
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String beginStr = in.next();
        String endStr = in.next();
        Set<String> dict = new HashSet<>();
        for (int i = 0; i < n; i++) {
            dict.add(in.next());
        }

        if (beginStr.equals(endStr)) {
            System.out.println(1);
            in.close();
            return;
        }

        Queue<String> q = new ArrayDeque<>();
        q.offer(beginStr);
        dict.remove(beginStr); // 起点已在队列，避免回头
        int ans = 1; // 序列长度，含 beginStr

        while (!q.isEmpty()) {
            int size = q.size();
            ans++;
            for (int k = 0; k < size; k++) {
                String cur = q.poll();
                char[] arr = cur.toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    char old = arr[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == old) {
                            continue;
                        }
                        arr[i] = c;
                        String nxt = new String(arr);
                        // 终点可以不在字典里（样例 endStr=def 就不在 strList 中）
                        if (nxt.equals(endStr)) {
                            System.out.println(ans);
                            in.close();
                            return;
                        }
                        if (!dict.contains(nxt)) {
                            continue;
                        }
                        q.offer(nxt);
                        dict.remove(nxt); // 每个词只用一次
                    }
                    arr[i] = old;
                }
            }
        }
        System.out.println(0);
        in.close();
    }
}

import java.util.*;

public class Main {
    static List<List<Integer>> graph;
    static boolean[] vis;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < k; i++) {
            int s = in.nextInt();
            int t = in.nextInt();
            graph.get(s).add(t);
        }

        vis = new boolean[n + 1];
        dfs(1);

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) {
                cnt++;
            }
        }
        int ans = (cnt == n) ? 1 : -1;
        System.out.println(ans);
        in.close();
    }

    static void dfs(int u) {
        vis[u] = true;
        for (int v : graph.get(u)) {
            if (!vis[v]) {
                dfs(v);
            }
        }
    }
}

import java.util.*;

public class Main {
    static int[] parent;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < m; i++) {
            int s = in.nextInt();
            int t = in.nextInt();
            union(s, t);
        }
        int source = in.nextInt();
        int destination = in.nextInt();
        int ans = (find(source) == find(destination)) ? 1 : 0;
        System.out.println(ans);
        in.close();
    }

    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    static void union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra != rb) {
            parent[rb] = ra;
        }
    }
}

import java.util.*;

public class Main {
    static int[] parent;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        int ansS = 0;
        int ansT = 0;
        for (int i = 0; i < n; i++) {
            int s = in.nextInt();
            int t = in.nextInt();
            if (find(s) == find(t)) { // 已连通再加边 → 成环
                ansS = s;
                ansT = t;
            } else {
                union(s, t);
            }
        }
        System.out.println(ansS + " " + ansT);
        in.close();
    }

    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    static void union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra != rb) {
            parent[rb] = ra;
        }
    }
}

import java.util.*;

public class Main {
    static int n;
    static int[] parent;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int[][] edges = new int[n][2];
        int[] inDegree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            edges[i][0] = in.nextInt();
            edges[i][1] = in.nextInt();
            inDegree[edges[i][1]]++;
        }

        // 指向入度为 2 的点的边，倒序收集（优先删靠后的）
        List<Integer> cand = new ArrayList<>();
        for (int i = n - 1; i >= 0; i--) {
            if (inDegree[edges[i][1]] == 2) {
                cand.add(i);
            }
        }

        if (!cand.isEmpty()) {
            // 先试删更靠后的 cand.get(0)
            if (isTreeAfterRemove(edges, cand.get(0))) {
                System.out.println(edges[cand.get(0)][0] + " " + edges[cand.get(0)][1]);
            } else {
                System.out.println(edges[cand.get(1)][0] + " " + edges[cand.get(1)][1]);
            }
        } else {
            // 无入度 2：删构成有向环的那条边
            removeCycleEdge(edges);
        }
        in.close();
    }

    static void init() {
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    static boolean same(int a, int b) {
        return find(a) == find(b);
    }

    static void union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra != rb) {
            parent[rb] = ra;
        }
    }

    // 删掉下标 deleteIdx 的边后，剩余边是否无环（有向树）
    static boolean isTreeAfterRemove(int[][] edges, int deleteIdx) {
        init();
        for (int i = 0; i < n; i++) {
            if (i == deleteIdx) {
                continue;
            }
            if (same(edges[i][0], edges[i][1])) {
                return false; // 仍成环
            }
            union(edges[i][0], edges[i][1]);
        }
        return true;
    }

    static void removeCycleEdge(int[][] edges) {
        init();
        for (int i = 0; i < n; i++) {
            if (same(edges[i][0], edges[i][1])) {
                System.out.println(edges[i][0] + " " + edges[i][1]);
                return;
            }
            union(edges[i][0], edges[i][1]);
        }
    }
}

import java.io.*;
import java.util.*;

public class Main {
    static int[] parent;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int[][] edges = new int[e][3]; // [u, v, w]
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            edges[i][0] = Integer.parseInt(st.nextToken());
            edges[i][1] = Integer.parseInt(st.nextToken());
            edges[i][2] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));

        parent = new int[v + 1];
        for (int i = 1; i <= v; i++) {
            parent[i] = i;
        }

        int ans = 0;
        int used = 0;
        for (int[] edge : edges) {
            int a = find(edge[0]);
            int b = find(edge[1]);
            if (a == b) {
                continue;
            }
            parent[b] = a;
            ans += edge[2];
            used++;
            if (used == v - 1) {
                break;
            }
        }
        System.out.println(ans);
    }

    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        int[] inDegree = new int[n];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            graph.get(s).add(t); // 先 S 后 T
            inDegree[t]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
            }
        }

        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int cur = q.poll();
            order.add(cur);
            for (int nxt : graph.get(cur)) {
                inDegree[nxt]--;
                if (inDegree[nxt] == 0) {
                    q.offer(nxt);
                }
            }
        }

        if (order.size() != n) {
            System.out.println(-1);
        } else {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if (i > 0) {
                    sb.append(' ');
                }
                sb.append(order.get(i));
            }
            System.out.println(sb); // 行末无空格
        }
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int s = in.nextInt();
            int e = in.nextInt();
            int v = in.nextInt();
            graph.get(s).add(new int[]{e, v}); // 有向边 s→e，耗时 v
        }

        final int INF = 0x3f3f3f3f;
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[]{0, 1}); // {当前距离, 节点}

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0];
            int u = cur[1];
            if (d > dist[u]) {
                continue; // 过期状态
            }
            for (int[] edge : graph.get(u)) {
                int nxt = edge[0];
                int w = edge[1];
                if (dist[nxt] > dist[u] + w) {
                    dist[nxt] = dist[u] + w;
                    pq.offer(new int[]{dist[nxt], nxt});
                }
            }
        }

        int ans = dist[n] == INF ? -1 : dist[n];
        System.out.println(ans);
        in.close();
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            edges[i][0] = in.nextInt();
            edges[i][1] = in.nextInt();
            edges[i][2] = in.nextInt();
        }

        final int INF = 0x3f3f3f3f;
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;

        // n-1 轮松弛；无负环时最短路最多 n-1 条边
        for (int i = 1; i <= n - 1; i++) {
            boolean updated = false;
            for (int[] e : edges) {
                int s = e[0];
                int t = e[1];
                int v = e[2];
                if (dist[s] == INF) {
                    continue; // 尚未从 1 到达 s
                }
                if (dist[t] > dist[s] + v) {
                    dist[t] = dist[s] + v;
                    updated = true;
                }
            }
            if (!updated) {
                break;
            }
        }

        if (dist[n] == INF) {
            System.out.println("unconnected");
        } else {
            int ans = dist[n];
            System.out.println(ans);
        }
        in.close();
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            edges[i][0] = in.nextInt();
            edges[i][1] = in.nextInt();
            edges[i][2] = in.nextInt();
        }

        final int INF = 0x3f3f3f3f;
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;

        for (int i = 1; i <= n - 1; i++) {
            for (int[] e : edges) {
                int s = e[0];
                int t = e[1];
                int v = e[2];
                if (dist[s] != INF && dist[t] > dist[s] + v) {
                    dist[t] = dist[s] + v;
                }
            }
        }

        boolean circle = false;
        for (int[] e : edges) {
            int s = e[0];
            int t = e[1];
            int v = e[2];
            if (dist[s] != INF && dist[t] > dist[s] + v) {
                circle = true; // 第 n 轮仍能松弛 → 1 可达负环
                break;
            }
        }

        if (circle) {
            System.out.println("circle");
        } else if (dist[n] == INF) {
            System.out.println("unconnected");
        } else {
            int ans = dist[n];
            System.out.println(ans);
        }
        in.close();
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            edges[i][0] = in.nextInt();
            edges[i][1] = in.nextInt();
            edges[i][2] = in.nextInt();
        }
        int src = in.nextInt();
        int dst = in.nextInt();
        int k = in.nextInt();

        final int INF = 0x3f3f3f3f;
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[src] = 0;

        // 最多 k 个中转点 → 最多 k+1 条边
        for (int step = 0; step <= k; step++) {
            int[] prev = dist.clone(); // 只用上一轮结果，防止本轮连跳
            for (int[] e : edges) {
                int s = e[0];
                int t = e[1];
                int v = e[2];
                if (prev[s] != INF && dist[t] > prev[s] + v) {
                    dist[t] = prev[s] + v;
                }
            }
        }

        if (dist[dst] == INF) {
            System.out.println("unreachable");
        } else {
            int ans = dist[dst];
            System.out.println(ans);
        }
        in.close();
    }
}

import java.util.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static List<List<int[]>> graph;
    static int n;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int m = in.nextInt();
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            int w = in.nextInt();
            graph.get(u).add(new int[]{v, w});
            graph.get(v).add(new int[]{u, w});
        }

        int[][] cache = new int[n + 1][]; // cache[s] = 从 s 出发的 dist
        int q = in.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            int start = in.nextInt();
            int end = in.nextInt();
            if (cache[start] == null) {
                cache[start] = dijkstra(start);
            }
            int ans = cache[start][end];
            sb.append(ans == INF ? -1 : ans).append('\n');
        }
        System.out.print(sb);
        in.close();
    }

    static int[] dijkstra(int src) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[]{0, src});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0];
            int u = cur[1];
            if (d > dist[u]) {
                continue;
            }
            for (int[] e : graph.get(u)) {
                int v = e[0];
                int w = e[1];
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        return dist;
    }
}

import java.util.*;

public class Main {
    static final int[][] DIRS = {
        {1, 2}, {1, -2}, {-1, 2}, {-1, -2},
        {2, 1}, {2, -1}, {-2, 1}, {-2, -1}
    };

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int a1 = in.nextInt();
            int a2 = in.nextInt();
            int b1 = in.nextInt();
            int b2 = in.nextInt();
            int ans = astar(a1, a2, b1, b2);
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
        in.close();
    }

    // 可采纳启发：骑士每步最多走 √5
    static int heuristic(int x, int y, int tx, int ty) {
        int dx = x - tx;
        int dy = y - ty;
        return (int) Math.ceil(Math.sqrt(dx * dx + dy * dy) / Math.sqrt(5.0));
    }

    static int astar(int sx, int sy, int tx, int ty) {
        if (sx == tx && sy == ty) {
            return 0;
        }
        int[][] best = new int[1001][1001]; // 到达该格的最少步
        for (int i = 0; i <= 1000; i++) {
            Arrays.fill(best[i], Integer.MAX_VALUE);
        }
        best[sx][sy] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        // {f, g, x, y}，f = g + h
        pq.offer(new int[]{heuristic(sx, sy, tx, ty), 0, sx, sy});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int g = cur[1];
            int x = cur[2];
            int y = cur[3];
            if (g != best[x][y]) {
                continue; // 过期状态
            }
            if (x == tx && y == ty) {
                return g;
            }
            for (int[] d : DIRS) {
                int nx = x + d[0];
                int ny = y + d[1];
                if (nx < 1 || nx > 1000 || ny < 1 || ny > 1000) {
                    continue;
                }
                int ng = g + 1;
                if (ng < best[nx][ny]) {
                    best[nx][ny] = ng;
                    pq.offer(new int[]{ng + heuristic(nx, ny, tx, ty), ng, nx, ny});
                }
            }
        }
        return -1; // 棋盘连通，理论上走不到
    }
}

import java.util.*;

/** n 数之和通用模板：返回所有和为 target 的不重复 n 元组 */
class NSumTemplate {

    /**
     * @param nums   原数组（会被排序，调用方若需保留原序请先拷贝）
     * @param n      几数之和，n >= 2
     * @param target 目标和
     */
    public List<List<Integer>> nSum(int[] nums, int n, int target) {
        Arrays.sort(nums);
        return dfs(nums, n, (long) target, 0);
    }

    /**
     * 从 nums[start..] 中选 n 个数，使其和为 target
     */
    private List<List<Integer>> dfs(int[] nums, int n, long target, int start) {
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        // 至少还要剩 n 个数
        if (n < 2 || len - start < n) {
            return ans;
        }

        // 剪枝：当前区间最小 / 最大 n 个数之和越界则无解
        long minSum = 0;
        long maxSum = 0;
        for (int i = 0; i < n; i++) {
            minSum += nums[start + i];
            maxSum += nums[len - 1 - i];
        }
        if (target < minSum || target > maxSum) {
            return ans;
        }

        // 递归边界：两数之和 → 双指针
        if (n == 2) {
            int left = start;
            int right = len - 1;
            while (left < right) {
                long sum = (long) nums[left] + nums[right];
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    ans.add(Arrays.asList(nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
            return ans;
        }

        // n > 2：枚举第一个数，递归求 (n-1) 数之和
        for (int i = start; i <= len - n; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue; // 同层去重
            }
            List<List<Integer>> subLists = dfs(nums, n - 1, target - nums[i], i + 1);
            for (List<Integer> sub : subLists) {
                List<Integer> path = new ArrayList<>(n);
                path.add(nums[i]);
                path.addAll(sub);
                ans.add(path);
            }
        }
        return ans;
    }

    // -------- 力扣封装示例 --------

    // 15. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        return nSum(nums, 3, 0);
    }

    // 18. 四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        return nSum(nums, 4, target);
    }
}