P15777 [JAG 2025 Summer Camp #2] Arrange One More Office

你的公司在一栋大楼的一层提供办公室租赁服务。该楼层是一个矩形，被划分为大小相同的正方形网格单元。如果两个单元共享一条边，则称它们相邻。有些单元可能包含柱子。有些单元可能是空的，留待将来使用。其余单元用作办公室，每个办公室由两个相邻的、没有柱子的单元组成。 有一天，一位潜在客户来到你的公司并申请一间办公室。由于所有现有的办公室都已出租，你需要设立一间新的办公室。当然，如果存在两个相邻的空单元，你可以在那里设立一间办公室。但如果没有，或许可以通过重新安置一些现有的办公室来腾出空间增设一间办公室。话虽如此，因为公司必须向受影响的租户支付赔偿，所以重新安置方案应最小化受影响的办公室数量。 更正式地，你的任务是找到一个满足以下条件的重新安置方案： - 重新安置后，楼层包含 $k + 1$ 间办公室，其中 $k$ 是重新安置前的办公室数量。 - 包含柱子的单元集合保持不变。 - 每间办公室仍然由两个相邻的、没有柱子的单元组成。 - 办公室之间互不重叠。 - 在所有满足上述条件的可能方案中，**不受影响**的办公室数量最大化。这里，一间在重新安置前由某两个单元组成的办公室，如果在重新安置后这两个单元仍然属于同一间办公室，则称该办公室不受影响。 如果存在这样的方案，请找出一个。如果存在多个方案，输出任意一个即可。

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 500\,000$），表示测试用例的数量。随后是 $t$ 个测试用例。每个测试用例的格式如下： $$ \begin{aligned} & h \ w \\ & s_{1,1} s_{1,2} \cdots s_{1,w} \\ & s_{2,1} s_{2,2} \cdots s_{2,w} \\ & \vdots \\ & s_{h,1} s_{h,2} \cdots s_{h,w} \end{aligned} $$ 第一行包含两个整数 $h$ 和 $w$（$h \geq 1$，$w \geq 1$，$h \times w \leq 500\,000$），表示楼层由 $h$ 行 $w$ 列的单元组成。 接下来的 $h$ 行，每行包含 $w$ 个字符。我们用 $(r, c)$ 表示第 $r$ 行第 $c$ 列的单元。每个字符 $s_{r,c}$ 表示单元 $(r, c)$ 的信息，它是 ‘#’、‘.’、‘^’、‘v’、‘’ 中的一个。如果 $s_{r,c}$ 是 ‘#’，则 $(r, c)$ 是一个有柱子的单元。如果 $s_{r,c}$ 是 ‘.’，则 $(r, c)$ 是一个空单元。如果存在一间由 $(r, c)$ 和 $(r + 1, c)$ 组成的办公室，则 $s_{r,c}$ 是 ‘^’ 且 $s_{r+1,c}$ 是 ‘v’。如果存在一间由 $(r, c)$ 和 $(r, c + 1)$ 组成的办公室，则 $s_{r,c}$ 是 ‘’。 如果 $s_{r,c}$ 是 ‘^’，保证 $r \leq h - 1$ 且 $s_{r+1,c}$ 是 ‘v’。类似地，如果 $s_{r,c}$ 是 ‘v’，则 $r \geq 2$ 且 $s_{r-1,c}$ 是 ‘^’。如果 $s_{r,c}$ 是 ‘’。最后，如果 $s_{r,c}$ 是 ‘>’，则 $c \geq 2$ 且 $s_{r,c-1}$ 是 ‘

对于每个测试用例，如果不存在有效的重新安置方案，则在一行中输出 "No"。否则，先在一行中输出 "Yes"，然后按照与输入相同的格式（不含 $h$ 和 $w$ 的那一行）输出 $h$ 行。这 $h$ 行应描述重新安置后楼层的信息。如果存在多个有效的重新安置方案，输出任意一个均可。

翻译由 DeepSeek V3.2 完成