题目描述

给定一个 $n \times m$ 的网格，行编号从 $1$ 到 $n$，列编号从 $1$ 到 $m$。除最左列 $1$ 与最右列 $m$ 外，每一列至多有一个障碍物；最左列与最右列保证没有障碍物。

你从最左列的任意一个格子出发（行自选），目标是到达最右列的任意一个格子（行自选）。假设你当前在第 $i$ 行第 $j$ 列，每一步你可以选择下列三种操作之一：

• 向右：从 $(i,j)$ 走到 $(i,j+1)$；
• 向上：从 $(i,j)$ 走到 $(i-1,j)$；
• 向下：从 $(i,j)$ 走到 $(i+1,j)$。

不允许向左移动，且任何时刻都不能进入障碍格子,也不能走出网格之外。

共有 $k$ 个障碍（按列号从小到大排序后编号为 $i=0$ 到 $k-1$）。对每个障碍，你必须选择“从上方绕过”或“从下方绕过”。

若第 $i$ 个障碍在列 $c_i$、行 $r_i$：

• 选择“从上方绕过”时，你在列 $c_i$ 时的行编号必须始终 $< r_i$；
• 选择“从下方绕过”时，你在列 $c_i$ 时的行编号必须始终 $> r_i$。

不同列的选择相互独立，共有 $2^k$ 种方案。

你的任务：对每一种方案，计算在满足该方案所有限制下，从最左列某行到最右列某行的最小步数；若该方案下无可行路径，输出 -1。

输入格式

本题包含多组测试数据。输入第一行包含一个整数 $T$ ($1 \le T \le 5000$)，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含两个整数 $n, m$ ($1 \leq n \leq 100, 2 \leq m \leq 100$)，分别表示网格的行数与列数。

第二行包含一个整数 $k$ ($0 \leq k \leq \min(m - 2, 10)$)，表示障碍的数量。

接下来 $k$ 行第 $i$ 行包含两个整数 $r_i$, $c_i$ ($1 \le r_i \le n, 1 \le c_i \le m$)，表示在第 $r_i$ 行第 $c_i$ 列有一个障碍。保证 $1 < c_1 < c_2 < \ldots < c_k < m$。

对于所有测试数据，保证 $\sum n \cdot m \leq 5000$，注意对于所有测试数据的 $k$ 之和并没有约束。

输出格式

对于每组测试，输出一行，包含 $2^k$ 个整数，依次表示编号从 $0$ 到 $2^k-1$ 的每一种方案的最小步数。相邻数字之间用一个空格分隔。若某种方案无解，则输出 $-1$。

方案编号说明：每种方案可看作一个长度为 $k$ 的二进制数。二进制数从低位到高位依次对应第 $0, 1, ..., k-1$ 个障碍。某一位为 $0$ 表示从上方绕过该障碍；为 $1$ 表示从下方绕过。

例如：若 $k = 3$，则共有 $2^3 = 8$ 种方案，对应如下

$$\begin{array}{|c|c|c|} \hline 方案编号 & 二进制表示（低位→高位） & 绕行选择（第\ 0, 第\ 1, 第\ 2\ 障碍） \\ \hline 0 & 000 & 上, 上, 上 \\ \hline 1 & 100 & 下, 上, 上 \\ \hline 2 & 010 & 上, 下, 上 \\ \hline 3 & 110 & 下, 下, 上 \\ \hline 4 & 001 & 上, 上, 下 \\ \hline 5 & 101 & 下, 上, 下 \\ \hline 6 & 011 & 上, 下, 下 \\ \hline 7 & 111 & 下, 下, 下 \\ \hline \end{array}$$

程序应按照方案编号从小到大的顺序输出每种方案的最小步数。

3
3 6
2
3 4
2 5
3 4
1
1 2
3 6
2
3 2
1 5

5 -1 -1 -1
-1 3
-1 -1 5 -1