题意重述

我们有一个 $n \times m$ 的网格，边界上有 $2d$ 个格子，它们包含了 $d$ 对数字 $1,1,2,2,\dots,d,d$。
要求画出 $d$ 条简单路径（不可自交、不可与其他路径共享任何格子），每条路径连接相同数字的两个格子，只能走上下左右四个方向，路径不能走出网格。
需要输出一种可行的方案，或者判断不可能。

---

关键观察

1. 数字都在边界：这意味着每条路径的起点和终点都在网格的外圈（第一行、最后一行、第一列、最后一列）。
2. 不相交路径：这是 Number Link 问题，已知在一般网格上是 NP 完全的，但端点都在边界时，可能有特殊的多项式解法。
3. 构造性：题目要求输出方案，$n,m$ 可达 $2000$，需要 $O(nm)$ 或 $O((n+m)d)$ 的算法。

---

已知结论（边界数字情况）

对于端点都在边界的 Number Link 问题，有一个经典构造方法：
外层剥皮法（Peeling Method）

思路如下：

• 将网格看作一层层“洋葱圈”，从外到内逐层处理。
• 在外层边界上，将相邻的相同数字配对，让它们的路径沿着当前层的外侧走（尽量贴近网格外侧，不进入内部）。
• 移除这些路径占用的格子（视为障碍），得到一个小一圈的子网格，递归处理内层。

---

具体构造步骤

1. 边界序列提取与配对

沿着网格的边界顺时针走一圈，记录遇到的数字（如果没有数字记为 0），得到一个长度为 $2(n+m)-4$ 的序列。
由于每个数字出现两次，我们要在这个序列中找出 $d$ 个配对，使得：

• 每个数字的两个位置配成一对。
• 配对时，路径可以在当前层外侧走而不互相交叉，并且不会把未配对的数字困在内层无法连接。

配对规则：
类似于括号匹配——在边界序列中，如果两个相同的数字相邻（中间没有未配对的数字），则可以将它们配对，路径沿着当前外层直接连接。
配对后，将这两个位置从序列中移除，继续找新的相邻相同数字。

这种贪心配对可以保证路径不交叉，并且不会阻挡内层数字的连接。

---

2. 路径构造

对于一对配对的数字（比如都在最外层边界上），它们可能：

• 在同一行（或同一列）：直接画一条水平（或垂直）直线连接（如果中间格子未被占用）。
• 不在同一行/列：路径需要沿外侧拐弯。

为了不占用内部空间，我们让路径紧贴外侧边界走：
例如，从 $(1,y_1)$ 到 $(1,y_2)$，如果 $y_1 < y_2$，路径可以向右走；但如果它们在对边，则需要绕网格外圈走，但这会占用其它边界格子，可能与其他路径冲突。
因此，我们采用逐层剥离策略：每次只连接当前外层相邻的配对，避免长距离绕圈。

---

3. 递归处理

每次连接一些配对后，将这些路径占用的格子从网格中移除，得到一个新的子网格（可能不再是矩形，但可以看作是去掉外层一些格子后的形状）。
继续在新的外层边界上提取数字序列，重复配对和连接过程。

如果某一步无法找到任何相邻相同数字配对，则可能需要回溯或重新配对，但已知结论：如果初始边界序列可以通过这种贪心完全配对，则一定有解。

---

4. 无解的判断

无解的情况发生在：
在边界序列中，无论如何配对，都会导致剩余的数字被困在内层，且它们无法连接（因为路径不能交叉，且外层被阻塞）。
一个充分必要条件（根据相关论文）是：
将边界序列视为一个环，存在一种配对方式使得配对间的区间不交叉（即配对是非交叉匹配），并且在剥去外层路径后，内层仍然满足这个性质。

但实际上，我们可以直接用贪心配对法尝试构造，如果在某层找不到任何相邻相同数字，则宣布无解。

---

算法步骤总结

1. 读入 $n,m,d$ 和 $d$ 对坐标。
2. 标记每个数字的位置。
3. 进行递归构造：
   • 提取当前层边界序列（顺时针）。
   • 在序列中不断寻找相邻相同数字，配对并构造路径（路径贴着当前外层走）。
   • 如果序列中找不到相邻相同数字，则尝试其他配对策略？若还不行则输出 Impossible。
   • 将路径占用的格子标记为已使用，得到新的边界。
4. 重复直到所有数字配对完成。
5. 输出网格字符表示（用 <, >, ^, v, 7, L, r, J, -, |, . 表示路径方向与类型）。

---

复杂度

每连接一对数字，需要 $O(1)$ 或 $O(L)$（$L$ 为路径长度）。
总路径长度 $O(nm)$，所以构造复杂度 $O(nm)$，可以接受 $n,m \le 2000$。

---

样例解释

样例 1 输出：

Possible
.r<..
.L7.v
r-J.|
|...|
^...|
><>-J

这里显示了 3 条路径，每对数字被连接，路径不相交。

样例 2 输出 Impossible，因为边界数字的排列无法形成非交叉配对，导致路径必然交叉或阻塞。

---

实现细节

• 需要维护网格状态（空闲、路径占用、数字位置）。
• 路径表示时要注意转弯字符（7, L, r, J, -, |）的正确使用。
• 边界提取时要注意角格子不要重复计算。

---

总结

本题是 Number Link 问题在端点位于边界时的特殊情形，可用贪心剥层法构造。
关键点：

1. 按层处理。
2. 在每层边界序列中找相邻相同数字配对。
3. 路径紧贴当前外层走。
4. 若某层无法配对则无解。

---