CF1770H.Koxia, Mahiru and Winter Festival

Wow, what a big face!

Kagura Mahiru

Koxia and Mahiru are enjoying the Winter Festival. The streets of the Winter Festival can be represented as a $n \times n$ undirected grid graph. Formally, the set of vertices is ${(i,j) \; | \; 1 \leq i,j\leq n }$ and two vertices $(i_1,j_1)$ and $(i_2,j_2)$ are connected by an edge if and only if $|i_1-i_2|+|j_1-j_2|=1$.

A network with size $n = 3$.

Koxia and Mahiru are planning to visit The Winter Festival by traversing $2n$ routes. Although routes are not planned yet, the endpoints of the routes are already planned as follows:

• In the $i$-th route, they want to start from vertex $(1, i)$ and end at vertex $(n, p_i)$, where $p$ is a permutation of length $n$.
• In the $(i+n)$-th route, they want to start from vertex $(i, 1)$ and end at vertex $(q_i, n)$, where $q$ is a permutation of length $n$.

A network with size $n = 3$, points to be connected are shown in the same color for $p = [3, 2, 1]$ and $q = [3, 1, 2]$.

Your task is to find a routing scheme — $2n$ paths where each path connects the specified endpoints. Let's define the congestion of an edge as the number of times it is used (both directions combined) in the routing scheme. In order to ensure that Koxia and Mahiru won't get too bored because of traversing repeated edges, please find a routing scheme that minimizes the maximum congestion among all edges.

An example solution — the maximum congestion is $2$, which is optimal in this case.

哇，好大的脸！

神乐麻里

小糸和麻里正在享受冬季祭典。冬季祭典的街道可以建模为一个 $n \times n$ 的无向网格图。形式化地说，顶点集为 $\{(i,j) \mid 1 \leq i,j \leq n\}$，且当且仅当 $|i_1-i_2|+|j_1-j_2|=1$ 时，顶点 $(i_1,j_1)$ 与 $(i_2,j_2)$ 之间存在一条边。

规模 $n = 3$ 的网络。

小糸和麻里计划通过 $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$ 条路径，使得每条路径均连接其指定的端点。我们定义一条边的拥塞度为该边在整套路由方案中被使用的总次数（两个方向合并计算）。为了确保小糸和麻里不会因反复经过相同边而感到乏味，请你找出一种使所有边中最大拥塞度最小化的路由方案。

一个示例解——最大拥塞度为 $2$，在此情形下是最优的。

The first line contains an integer $n$ ($2 \leq n \leq 200$) — the size of the network.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \leq p_i \leq n$).

The third line contains $n$ integers $q_1, q_2, \dots, q_n$ ($1 \leq q_i \leq n$).

It is guaranteed that both $p$ and $q$ are permutations of length $n$.

第一行包含一个整数 $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$ 的排列。

Output $2n$ lines, each line describing a route.

The first $n$ lines should describe the connections from top to bottom. The $i$-th line should describe the route starting at vertex $(1, i)$ and ending at vertex $(n, p_i)$.

The next $n$ lines should describe the connections from left to right. The $(i+n)$-th line should describe the route starting at vertex $(i, 1)$ and ending at vertex $(q_i, n)$.

Each line describing a route should start with an integer $k$ ($2 \le k \le 10^5$) — the number of vertices the route passes, including the starting and ending vertices. Then output all the vertices on the route in order. In other words, if the route is $(x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \dots \rightarrow (x_k, y_k)$, then output $k~x_1~y_1~x_2~y_2 \ldots x_k~y_k$. Note that $|x_i-x_{i+1}|+|y_i-y_{i+1}| = 1$ should holds for $1 \le i \lt k$.

If there are multiple solutions that minimize the maximum congestion, you may output any.

输出 $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$。注意：对所有 $1 \le i < k$，需满足 $|x_i-x_{i+1}|+|y_i-y_{i+1}| = 1$。

若存在多个解均能最小化最大拥塞度，则输出任意一个即可。

The first example corresponds to the figures in the problem statement.

The output for examples $2$ and $3$ respectively are visualized below:

Sample output for examples $2$ and $3$. Maximum congestions are $2$ and $1$ respectively.

第一个示例对应题目描述中的图示。

示例 $2$ 和 $3$ 的输出分别如下图所示：

示例 $2$ 和 $3$ 的输出样例。最大拥塞度分别为 $2$ 和 $1$。