Background

Translated from Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) D2T1. $\texttt{5s,0.5G}$.

• Input format has minor adjustments.
• Official data is incorrect. Some output files were generated using hhoppitree's code, but optimality is not guaranteed. If you can provide better code, feel free to contact the problem搬运人.

Problem Description

Construct a $N \times M$ grid graph with edge weights all being $1$, where each edge can either exist or not.

Under the condition of connectivity, maximize the shortest path length from $(A, B)$ to $(C, D)$.

Here, the path length is defined as the number of nodes traversed by the path.

Input and Output Format

Input Format

This problem contains multiple test cases within a single test point.

The first line contains two integers $\mathrm{type}$ and $T$, representing the type of test data and the number of test cases, respectively.

The next $T$ lines, each containing six integers $N, M, A, B, C, D$, describe the details as per the problem statement.

Output Format

For each test case, output several lines.

• $\mathrm{type}=0$: "Construction" type data

For this type of data, you need to construct a grid graph. Output $(2N-1)$ lines, each containing $(3M-2)$ characters.

Among these, the $(2i-1)$-th line's $(3j-2)$-th character represents the point $(i, j)$. When $(i, j)=(A, B)$ or $(S, T)$, use * (ASCII 42); otherwise, use o (ASCII 111).

For two points $(i, j)$ and $(i, j+1)$ on the same line, if there is an edge, fill the two spaces between them with -- (ASCII 45); otherwise, leave them unfilled.

For two points $(i, j)$ and $(i+1, j)$ in the same column, if there is an edge, fill the space between them with | (ASCII 124); otherwise, leave it unfilled.

Unfilled areas should be filled with spaces. Do not output extra spaces or blank lines.

Refer to the sample output for examples.

• $\mathrm{type}=1$: "Traditional" type data

Output a single integer on one line, representing the longest path length.

Sample Input and Output

Sample Input #1

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

Sample Output #1

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

Sample Input #2

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

Sample Output #2

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

Sample Input #3

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

Sample Output #3

5
9

Notes

For $100\%$ of the data, the following conditions are guaranteed:

• $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)$.

Scoring Method

• $\mathrm{type}=0$: "Construction" type data

Let $d_i$ be the shortest path length in the scheme you constructed for the $i$-th test case, and $D_i$ be the possible longest shortest path length. Let

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

When $K = 1$, you get full marks for that test point; otherwise, you get $0.7 \cdot K$ times the test point score.

The score for each subtask is the minimum of the scores for all test points.

For example, the output for Sample 1 gets full marks; for Sample 2, $\displaystyle k = \frac{1}{2} \left( \frac{3}{5} + \frac{5}{9} \right) = \frac{31}{45}$, which will get $\displaystyle 0.7 \cdot \frac{31}{45} \approx 0.482$ times the test point score.

• $\mathrm{type}=1$: "Traditional" type data

Scored the same way as traditional problems.

见题面 Input 部分

见题面 Output 部分