题目描述

给定一个 $n\times m$ 的矩阵。矩阵中每一个位置 $(x,y)$ 均有一个数 $a_{x,y}$，保证 $0\le a_{x,y}\le n\cdot m-1$ 且任意两个 $a_{x,y}$ 不相等。

现在你开始在矩阵中行走。你可以从任意位置开始，每一步移动到与当前位置相邻$^{[1]}$的四个格子中任意一个。

请你找到一条最长的好$^{[2]}$的行走路径 $(c_1,c_2,\cdots,c_k)$。若存在多条最长的路径满足要求，输出字典序$^{[3]}$最小的。

多组数据。

$[1]$：定义两个格子 $(x,y)$ 和 $(z,w)$ 是相邻的，当且仅当 $|x-y|+|z-w|=1$。

$[2]$：定义一条路径 $(c_1,c_2,\cdots,c_k)$ 是好的，当且仅当对于 $\forall 1\le i\lt k$，$c_i$ 与 $c_{i+1}$ 对应的位置相邻且 $c_i\lt c_{i+1}$。

$[3]$：定义路径 $(c_1,c_2,\cdots,c_k)$ 比 $(d_1,d_2,\cdots,d_k)$ 小，当且仅当 $\exists 1\le i\le n$，使得 $\forall 1\le j\lt i,c_j=d_j$ 且 $c_i\lt d_i$。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来包含 $T$ 组数据。对于每组数据：

第一行两个整数 $n$ 和 $m$。

后面 $n$ 行，每行 $m$ 个整数，表示矩阵 $a$。

输出格式

对于每组数据：

第一行一个数 $k$，表示所求的路径长度。

第二行 $k$ 个数 $c_1,c_2,\cdots,c_k$，表示所求路径。

样例输入 #1

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

样例输出 #1

7
0 1 3 4 5 6 7
2
0 2

样例解释 #1

第一组数据：

0 → 1 → 3
        ↓
2   7   4
    ↑   ↓
8   6 ← 5

第二组数据：

0   3
↓    
2   1

容易发现没有更长或字典序更小的解。

样例输入 #2

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

样例输出 #2

5
0 1 2 5 8
3
3 4 7

数据规模与约定

本题目采用 $\text{subtask}$ 测试。

对于 $100\%$ 的数据，$1\le T\le 10$，$1\le n\times m\le 2\times 10^5$。

具体数据范围如下：

$\text{subtask 1(20pts)}$：$1\le n\times m\le 10$；

$\text{subtask 2(20pts)}$：$1\le n\times m\le 1000$；

$\text{subtask 3(10pts)}$：$1\le n\le 2$；

$\text{subtask 4(10pts)}$：$1\le n\le 4$；

$\text{subtask 5(40pts)}$：无特殊限制。