题目重述

有一个二维平面，上面放置了 $n$ 块与坐标轴成 $45^\circ$ 的挡板，每块挡板用中点坐标 $(x_i, y_i)$ 和字符 \ 或 / 描述。球沿平行于坐标轴的方向运动，撞上挡板会转向 $90^\circ$，且挡板两面均可反弹。

现在要用 $4$ 种颜色给挡板上色，要求对于球运动形成的每一个循环，循环中球经过每种颜色的次数相同且为偶数。若不存在这样的涂色方案，输出 $-1$。

---

问题转化

1. 运动规律分析

球的运动方向只有 4 种：上、下、左、右。
挡板的作用是改变运动方向，具体规则为：

• 对于 \ 挡板：
  • 水平方向来球 → 垂直方向出球
  • 垂直方向来球 → 水平方向出球
• 对于 / 挡板：
  • 水平方向来球 → 垂直方向出球（但反向）
  • 垂直方向来球 → 水平方向出球（但反向）

由于挡板两面都可反弹，每个挡板会在两种不同的运动情景中被用到。

---

2. 坐标变换与二分图建模

为了便于处理，进行坐标变换：

• 令 $u = x + y$
• 令 $v = x - y$

在 $(u, v)$ 坐标系中：

• 球的运动变为沿 $u$ 轴或 $v$ 轴方向移动
• 挡板连接相邻的 $(u, v)$ 坐标点

更具体地，我们可以建立二分图：

• $U$ 类节点：所有可能的 $u$ 值
• $V$ 类节点：所有可能的 $v$ 值
• 边：每个挡板对应一条连接 $U$ 节点和 $V$ 节点的边
  • \ 挡板：连接 $u = x+y$ 和 $v = x-y$
  • / 挡板：连接 $u = x+y$ 和 $v = x-y+1$（通过这个 $+1$ 偏移保证图的二分性）

---

3. 图的性质

在这个二分图中：

• 每个节点的度数都是偶数
• 原因：在原始运动中，每个“位置+方向”状态都有唯一的前驱和后继，保证进出平衡
• 因此，每个连通分量都是一个欧拉回路
• 球的运动轨迹对应图中的欧拉回路

---

4. 颜色要求的数学表达

设一个循环的长度（经过的挡板数）为 $L$。
要求：

1. 每种颜色出现次数相同：$L$ 必须是 $4$ 的倍数
2. 每种颜色出现次数为偶数：$L$ 必须是 $8$ 的倍数

因此，每个连通分量的边数必须是 8 的倍数。

---

解法步骤

1. 建立图模型

• 将每个挡板转化为一条连接 $U$ 节点和 $V$ 节点的边
• 记录每条边对应的原始挡板编号

2. 检查连通分量

• 找出图的所有连通分量
• 对每个分量计算边数 $m$
• 如果存在某个 $m \bmod 8 \neq 0$，则无解，输出 $-1$

3. 构造涂色方案

对每个连通分量：

1. 找到一条欧拉回路
2. 沿着回路的边顺序，按 $1, 2, 3, 4, 1, 2, 3, 4, \ldots$ 循环染色
3. 将颜色赋给对应的挡板

4. 输出结果

按输入顺序输出每个挡板的颜色。

---

正确性证明

1. 颜色分布均匀性

• 每个循环长度 $L = 8k$
• 按 $1,2,3,4$ 循环染色，每种颜色恰好出现 $2k$ 次
• 满足“次数相同且为偶数”

2. 覆盖所有循环

• 图的每个连通分量是一个欧拉回路
• 球从任意边开始运动，都会遍历整个回路的边
• 因此我们的染色方案覆盖了所有可能的循环

---

时间复杂度

• 建图：$O(n)$
• 连通分量分析：$O(n)$
• 欧拉回路：$O(n)$
• 总复杂度：$O(n)$（使用哈希表存储节点）

---

总结

本题的关键在于通过坐标变换将物理运动转化为图论问题，利用欧拉回路的性质保证解的存在性条件（每个节点度数为偶数），再通过模 8 条件判断可行性。染色方案则通过简单的循环分配实现，保证了颜色分布的均匀性和偶数次要求。