Koxia 和 Mahiru 正在享受冬季祭典。冬季节日的街道可以表示为 $$$n \times n$$$ 无向网格图。形式上,顶点集是 $$$\{(i,j) \; | \; 1 \leq i,j\leq n \}$$$ 和两个顶点 $$$(i_1,j_1)$$$ 和 $$$(i_2,j_2)$$$ 通过边连接当且仅当 $$$|i_1-i_2|+|j_1-j_2|=1$$$。
大小为 $$$n = 3$$$ 的网络。
Koxia 和 Mahiru 计划通过 $$$2n$$$ 路线来参观冬季节日。虽然路线还没有规划,但路线的终点已经规划如下:
- 在第 $$$i$$$ 条路线中,他们希望从顶点 $$$(1, i)$$$ 开始并在顶点 $$$(n, p_i)$$$ 结束,其中 $$$p$$$ 是长度 $$$n$$$ 的排列。
- 在第 $$$(i+n)$$$ 条路线中,他们希望从顶点 $$$(i, 1)$$$ 开始并在顶点 $$$(q_i, n)$$$ 结束,其中 $$$q$$$ 是长度 $$$n$$$ 的排列。
大小为 $$$n = 3$$$ 的网络,对于 $$$p = [3, 2, 1]$$$ 和 $$$q = [3, 1, 2]$$$,要连接的点以相同颜色显示。
你的任务是找到一个路由方案 - $$$2n$$$ 路径,其中每条路径连接指定端点。让我们将边的拥塞定义为在路由方案中使用它的次数(两个方向的组合)。为了保证Koxia和Mahiru不会因为遍历重复的边而感到太无聊,请找到一种路由方案,使所有边之间的最大拥塞最小化。
示例解决方案 — 最大拥塞为 $$$2$$$,在这种情况下是最佳的。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 200$$$) — 网络的大小。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq n$$$)。
第三行包含 $$$n$$$ 整数 $$$q_1, q_2, \dots, q_n$$$ ($$$1 \leq q_i \leq n$$$)。
保证 $$$p$$$ 和 $$$q$$$ 都是长度为 $$$n$$$ 的排列。
输出
输出 $$$2n$$$ 行,每行描述一条路线。
前 $$$n$$$ 行应描述从上到下的连接。第 $$$i$$$ 行应描述从顶点 $$$(1, i)$$$ 开始并在顶点 $$$(n, p_i)$$$ 结束的路线。
接下来的 $$$n$$$ 行应该从左到右描述连接。第 $$$(i+n)$$$ 行应描述从顶点 $$$(i, 1)$$$ 开始并在顶点 $$$(q_i, n)$$$ 结束的路线。
描述路线的每一行应以整数 $$$k$$$ ($$$2 \le k \le 10^5$$$) 开头 - 路线经过的顶点数,包括起始和结束顶点。然后按顺序输出路径上的所有顶点。换句话说,如果路线是$$$(x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \dots \rightarrow (x_k, y_k)$$$,则输出$$$k~x_1~y_1~x_2~y_2 \ldots x_k~y_k$$$。请注意 $$$|x_i-x_{i+1}|+|y_i-y_{i+1}| = 1$$$ 对于 $$$1 \le i < k$$$ 应该成立。
如果有多个解决方案可以最小化最大拥塞,则可以输出任何一个。
示例
输入 #1
3 3 2 1 3 1 2
输出 #1
5 1 1 2 1 2 2 3 2 3 3 3 1 2 2 2 3 2 5 1 3 1 2 1 1 2 1 3 1 5 1 1 1 2 1 3 2 3 3 3 4 2 1 2 2 2 3 1 3 4 3 1 3 2 3 3 2 3
输入 #2
4 3 4 2 1 2 4 1 3
输出 #2
6 1 1 1 2 2 2 2 3 3 3 4 3 6 1 2 1 3 2 3 2 4 3 4 4 4 5 1 3 2 3 2 2 3 2 4 2 7 1 4 1 3 1 2 2 2 2 1 3 1 4 1 7 1 1 2 1 3 1 3 2 3 3 2 3 2 4 6 2 1 2 2 3 2 4 2 4 3 4 4 6 3 1 3 2 3 3 3 4 2 4 1 4 5 4 1 4 2 4 3 3 3 3 4
输入 #3
3 1 2 3 1 2 3
输出 #3
3 1 1 2 1 3 1 3 1 2 2 2 3 2 3 1 3 2 3 3 3 3 1 1 1 2 1 3 3 2 1 2 2 2 3 3 3 1 3 2 3 3
注意
第一个示例对应于问题陈述中的数字。
示例 $$$2$$$ 和 $$$3$$$ 的输出分别可视化如下:
$$$2$$$ 和 $$$3$$$ 的示例输出。最大拥堵分别为 $$$2$$$ 和 $$$1$$$。