题目描述

你有一个 $n$ 行 $m$ 列的网格图。定义 $(x, y)$ 表示网格图中第 $x$ 行第 $y$ 列的格子，则网格图左上角的格子可被表示为 $(1, 1)$，右下角的格子可被表示为 $(n, m)$。

现在这个网格图被挖掉了一个格子 $(wx, wy)$，你需要判断是否存在一条从 $(sx, sy)$ 出发的哈密顿路径，如果有则还需要输出任意一组合法方案（即不需经过也不能经过 $(wx, wy)$ 的且起点为 $(sx, sy)$ 的哈密顿路径）。

输入格式

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

接下来 $T$ 行，每行六个正整数 $n,m,wx,wy,sx,sy$，含义如题目描述中所示。其中 $1\le wx,sx\le n, 1\le wy, sy\le m, (wx,wy)\neq (sx,sy)$。

输出格式

对于每组数据：

若无解则仅输出一行一个整数 $-1$，否则：

先输出一行一个正整数 $len$，表示哈密顿路径长度，显然 $len = nm - 1$；

接下来 $len$ 行，每行两个正整数 $(x, y)$，表示每一步所走到的格子的坐标，显然第一行应输出 $(sx, sy)$。

3
2 5 2 3 1 1
4 4 2 2 1 1
5 5 1 1 5 1

9
1 1
2 1
2 2
1 2
1 3
1 4
2 4
2 5
1 5
-1
24
5 1
4 1
3 1
2 1
2 2
1 2
1 3
1 4
1 5
2 5
3 5
4 5
5 5
5 4
5 3
5 2
4 2
3 2
3 3
2 3
2 4
3 4
4 4
4 3

数据范围与提示

对于所有数据，保证 $1\le n, m\le 200$，$\sum (n + m)\le 2000$。