题目背景

译自 Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) D2T1。$\texttt{5s,0.5G}$。

• 输入格式有微调。
• 官方数据有误。 部分 out 文件是使用树姐姐 hhoppitree 的代码生成的。如果出现了分数 $\gt 100$ 的情况，欢迎联系搬题人更新数据。

题目描述

构造一个 $N\times M$ 的网格图，边权均为 $1$，每条边可以存在或者不存在。

在连通的前提下，最大化 $(A,B)$ 到 $(C,D)$ 的最短路长度。

此处路径长度定义为路径经过的节点个数。

输入格式

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

第一行，两个整数 $\mathrm{type},T$，表示测试数据类型和测试数据组数。

接下来 $T$ 行，每行 $6$ 个整数 $N,M,A,B,C,D$，含义见题面。

输出格式

每组测试数据输出若干行。

• $\mathrm{type}=0$：「构造」类数据

此类数据中，你需要构造一个网格图。输出 $(2N-1)$ 行，每行 $(3M-2)$ 个字符。

其中，第 $(2i-1)$ 行的第 $(3j-2)$ 个字符代表点 $(i,j)$。当 $(i,j)=(A,B)$ 或 $(S,T)$ 时，用 *（ASCII 42）表示；否则用 o（ASCII 111）表示。

对于同一行的两个点 $(i,j),(i,j+1)$，若有边，则用 --（ASCII 45）填充它们之间的两个空格；否则不填充。

对于同一列的两个点 $(i,j),(i+1,j)$，若有边，则用 |（ASCII 124）填充它们之间的一个空格；否则不填充。

未填充的区域均用空格补齐。不要输出多余的空格和空行。

可参阅样例输出。

• $\mathrm{type}=1$：「传统」类数据

只需要输出一行一个整数，表示最长路长度。

0 2
2 3 1 1 2 2
3 3 1 1 3 3

*--o--o
      |
o  *--o
*  o--o
|  |  |
o  o  o
|  |  |
o--o  *

0 2
2 3 1 1 2 2
3 3 1 1 3 3

*--o  o
   |
o  *  o
*  o  o
|
o  o--o
|  |  |
o--o  *

1 2
2 3 1 1 2 2
3 3 1 1 3 3

5
9

提示

对于 $100\%$ 的数据，保证：

• $1\le N,M\le 5\, 000$；
• $1\le Q\le 1\, 600$；
• $1\le A,C\le N$，$1\le B,D\le M$；
• $(A,B)\neq (C,D)$。

子任务编号	$N\cdot M\in$	$M\le$	$\mathrm{type}=$	分值
$1$	$[2,100]$	$5\, 000$	$0$	$20$
$2$	$[2,1\, 000]$			$25$
$3$	$[2,15\, 000]$	$3$		$15$
$4$	$[2,100\, 000]$	$5\, 000$		$25$
$5$			$1$	$15$

【评分方式】

• $\mathrm{type}=0$：「构造」类数据

记 $d_i$ 为第 $i$ 组测试数据中，你构造的方案中的最短路长度，$D_i$ 为可能的最长最短路长度。记

$$K=\frac{1}{Q}\sum_{i=1}^Q\frac{d_i}{D_i}$$

当 $K=1$ 时，该测试点得满分；否则得 $0.7\cdot K$ 倍测试点得分的分数。

每个子任务的得分为所有测试点得分的 $\min$。

例如，样例 $1$ 的输出得满分；对于样例 $2$，$\displaystyle k=\frac{1}{2}\left(\frac{3}{5}+\frac{5}{9}\right)=\frac{31}{45}$，将得到 $\displaystyle 0.7\cdot \frac{31}{45}\approx 0.482$ 倍测试点得分的分数。

• $\mathrm{type}=1$：「传统」类数据

和传统题评分方式相同。