该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Description

这是一道 hack 题。你需要为特定题目的特定代码构造数据，使得特定代码无法给出正确的答案。此类情况包括：

1. 输出错误的结果；
2. 运行超时；
3. 内存超出限制；
4. 产生未定义行为。

未定义行为可能不能稳定触发。你若希望针对此方向进行 hack，构造了你认为正确的数据但无法成功，请联系出题组。

你应该提交一份代码，这份代码读入一个整数表示测试点编号，输出对应测试点的构造数据。

由于 Special Judge 的奇特实现，本题评测速度极慢。请耐心等待。如果你遇到 System Error，请尝试重新提交。

以下代码都是 MrPython 在 Codeforces 比赛中犯下的唐氏错误，你能找出这些错误并嘲讽他吗？

Subtask 1

Description

给定一个 $n \times m$ 的网格，其中每个格子 $(i, j)$ 上有一个整数 $a_{i,j}$。定义一条从左上角 $(1, 1)$ 到右下角 $(n, m)$ 的路径，要求路径上的每一步只能向下或向右移动。

对于一条路径，设其经过的格子上的数字序列为 $x_1, x_2, \dots, x_k$（其中 $k = n + m - 1$ 是路径长度），定义该路径的值为这些数字的最大公约数（GCD）。

目标是求出所有可能路径中路径值的最大值。

Constraints

• $1\le T\le 10^4$
• $1\le n,m\le 100$
• $1\le a_{i,j}\le 10^6$
• $\sum nm\le 2\times 10^5$
• 所有输入的数据均为整数。

Input

本题单个测试点有多组测试数据。

输入内容从标准输入给出。先读入数据组数 $T$。

对于每组数据，格式如下：

$ \boxed{\begin{aligned} & n {\quad} m \\ & a_{1,1} {\quad} a_{1,2} {\quad} \dots {\quad} a_{1,m} \\ & a_{2,1} {\quad} a_{2,2} {\quad} \dots {\quad} a_{2,m} \\ & ~ \vdots \\ & a_{n,1} {\quad} a_{n,2} {\quad} \dots {\quad} a_{n,m} \\ \end{aligned}} $

Output

对于每组数据，输出能得到的最大公因数。

Limits

• 时间限制：$2~\text{s}$；
• 空间限制：$256~\text{MiB}$。

Example

3
2 3
30 20 30
15 25 40
3 3
12 4 9
3 12 2
8 3 12
2 4
2 4 6 8
1 3 6 9

10
3
1

Target

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
int main(void) {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  size_t T;
  cin >> T;
  while (T--) {
    size_t n, m;
    cin >> n >> m;
    vector<vector<ui>> a(n, vector<ui>(m));
    for (vector<ui>& i : a)
      for (ui& j : i) cin >> j;
    vector<vector<set<ui>>> f(n, vector<set<ui>>(m));
    f[0][0].insert(a[0][0]);
    for (size_t i = 1; i < n; ++i)
      for (ui k : f[i - 1][0]) f[i][0].insert(gcd(k, a[i][0]));
    for (size_t j = 1; j < m; ++j)
      for (ui k : f[0][j - 1]) f[0][j].insert(gcd(k, a[0][j]));
    for (size_t i = 1; i < n; ++i)
      for (size_t j = 1; j < m; ++j) {
        for (ui k : f[i][j - 1]) f[i][j].insert(gcd(k, a[i][j]));
        for (ui k : f[i - 1][j]) f[i][j].insert(gcd(k, a[i][j]));
      }
    cout << *f.back().back().rbegin() << '\n';
  }
  return 0;
}

Subtask 2

Description

你有一个长度为 $n$ 的数组 $a$，其中所有元素均为非零整数。初始时你有 $0$ 个硬币，你需要重复以下操作直到数组为空：

• 设当前数组长度为 $m$。选择一个整数 $i$（$1 \le i \le m$），获得 $|a_i|$ 个硬币，然后：
  • 如果 $a_i < 0$，则将数组替换为 $[a_1, a_2, \ldots, a_{i - 1}]$（即删除从 $a_i$ 开始的后缀）；
  • 否则，将数组替换为 $[a_{i + 1}, a_{i + 2}, \ldots, a_m]$（即删除以 $a_i$ 结尾的前缀）。

求最终能获得的最大硬币数量。

Constraints

• $1 \le t \le 10^4$
• $1 \le n \le 2 \times 10^5$
• $-10^9 \le a_i \le 10^9$，$a_i \neq 0$
• $\sum n \leq 2 \times10^5$
• 所有输入的数据均为整数。

Input

本题单个测试点有多组测试数据。

输入内容从标准输入给出。先读入数据组数 $T$。

对于每组数据，格式如下：

$ \boxed{\begin{aligned} & n \\ & a_1 {\quad} a_2 {\quad} \dots {\quad} a_n \end{aligned}} $

Output

对于每组数据，输出能获得的最大硬币数量。

Limits

• 时间限制：$2~\text{s}$；
• 空间限制：$256~\text{MiB}$。

Example

3
6
3 1 4 -1 -5 -9
6
-10 -3 -17 1 19 20
1
1

23
40
1

Target

#include <cassert>
#include <cstddef>
#include <deque>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
istream& fin = cin;
ostream& fout = cout;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
int main(void) {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  size_t T;
  fin >> T;
  while (T--) {
    size_t n;
    fin >> n;
    deque<li> s = {0};
    fin >> s[0];
    for (size_t i = 1; i < n; ++i) {
      int x;
      fin >> x;
      if ((li)x * s.back() > 0)
        s.back() += x;
      else
        s.emplace_back(x);
    }
    uli pans = 0;
    if (!s.empty() && s.front() > 0) pans += s.front(), s.pop_front();
    if (!s.empty() && s.back() < 0) pans += -s.back(), s.pop_back();
    vector<pair<uli, uli>> v;
    for (auto it = s.begin(); it != s.end(); it += 2)
      v.emplace_back(-*it, *next(it));
    uli sum = 0;
    for (auto [i, j] : v) sum += i;
    uli ans = sum;
    for (auto [i, j] : v) {
      (sum -= i) += j;
      ans = max(ans, sum);
    }
    fout << pans + ans << '\n';
  }
  return 0;
}

Subtask 3

Description

将地铁图可以示为一个无向连通图，图中没有自环，顶点代表车站。任意两个顶点之间最多存在一条边。

若两个顶点之间存在边，则可以直接在对应的车站之间通行而无需经过其他车站。该城市的地铁采用颜色标记法：每条边具有特定颜色，同一颜色的所有边构成一条地铁线路。一条地铁线路不能包含不连通的边，且必须是原图的连通子图。

地铁图的示例如下图所示。

定义最优路线是经过最少数量地铁线路的路线。请计算从起点到终点车站所需经过的最少地铁线路数量。

Constraints

• $1 \le t \le 10^4$
• $2 \le n \le 2 \cdot 10^5$
• $1 \le m \le 2 \cdot 10^5$
• $1 \le u, v \le n,\ u \neq v$
• $1 \le c \le 2 \cdot 10^5$
• 同一颜色的所有边构成连通子图。
• 任意两顶点之间最多一条边。
• $\sum n \leq 2 \cdot 10^5$
• $\sum m \leq 2 \cdot 10^5$
• 输入数据均为整数。

Input

本题包含多组测试数据。

输入内容从标准输入读取。第一行包含整数 $t$ 表示测试用例数。

每个测试用例的格式如下：

$ \boxed{\begin{aligned} & n {\quad} m \\ & u_1 {\quad} v_1 {\quad} c_1 \\ & u_2 {\quad} v_2 {\quad} c_2 \\ & ~ \vdots \\ & u_m {\quad} v_m {\quad} c_m \\ & b {\quad} e \\ \end{aligned}} $

Output

对每个测试用例，输出一个整数 —— 从车站 $b$ 到车站 $e$ 的路线中，经过的地铁线路数量的最小值。

Example

5
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
1 3
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
1 6
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
6 6
4 3
1 2 1
1 3 1
4 1 1
2 3
6 7
1 2 43
1 3 34
4 6 43
6 3 43
2 3 43
5 3 43
4 5 43
1 6

1
2
0
1
1

3
7 9
2 4 1
3 6 1
2 3 5
1 7 1
4 7 1
2 5 4
5 4 4
3 4 1
3 7 1
5 3
6 5
6 5 83691
4 1 83691
5 4 83691
3 2 83691
4 3 83691
5 1
6 7
6 1 83691
6 2 83691
2 5 83691
5 6 83691
2 3 83691
5 4 83574
3 5 83691
1 4

2
1
2

Target

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
int main(void) {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  size_t T;
  cin >> T;
  while (T--) {
    size_t n, m;
    cin >> n >> m;
    vector<map<ui, vector<size_t>>> sn(n);
    while (m--) {
      size_t a, b;
      ui c;
      cin >> a >> b >> c;
      --a, --b, --c;
      sn[a][c].push_back(b), sn[b][c].push_back(a);
    }
    size_t s, t;
    cin >> s >> t;
    --s, --t;
    if (s == t) {
      cout << "0\n";
      continue;
    }
    vector<map<ui, ui>> dis(n);
    deque<pair<size_t, ui>> q;
    for (pair<ui, vector<size_t>> const &i : sn[s])
      q.emplace_back(s, i.first), dis[s][i.first] = 1;
    while (!q.empty()) {
      size_t p = q.front().first, c = q.front().second;
      q.pop_front();
      ui d = dis[p][c];
      for (size_t j : sn[p][c])
        if (!dis[j].count(c) || dis[j][c] > d)
          dis[j][c] = d, q.emplace_front(j, c);
      for (pair<ui, vector<size_t>> const &i : sn[p])
        if (i.first != c)
          for (size_t j : i.second)
            if (!dis[j].count(i.first) || dis[j][i.first] > d + 1)
              dis[j][i.first] = d + 1, q.emplace_back(j, i.first);
    }
    ui ans = numeric_limits<ui>::max();
    for (auto const &i : dis[t])
      ans = min(ans, i.second);
    cout << ans << '\n';
  }
  return 0;
}