你发来的题目是 COCI 2018/2019 Contest #1 T5「Teoretičar」，和之前我给出的那道「Praktični」不是同一题。这是二分图边着色问题的一个特殊版本。我来为你写这道题的题解。

题目大意

给定一个二分图，左部 $L$ 个点，右部 $R$ 个点，$M$ 条边。
要对边进行着色，使得每个顶点所关联的边的颜色互不相同。
设最小可能的颜色数是 $C$，令 $X$ 为 $\ge C$ 的最小 $2$ 的整次幂，我们只需要用不超过 $X$ 种颜色给出一个方案。

思路分析

1. 理论基础

这是一个经典的二分图边着色问题，由 Kőnig's line coloring theorem 可知：

对于二分图，最小边着色数等于最大度数 $\Delta$。

因此 $C = \Delta$（最大度数）。
题目要求：使用颜色数 $K$，且 $K$ 是 $\ge \Delta$ 的最小 $2$ 的整次幂，即
[ K = 2^{\lceil \log_2 \Delta \rceil} ] 我们可以使用 $K$ 种颜色来完成着色，而 $K \le 2\Delta$。

2. 构造方法

我们需要构造一个 $K$-边着色的方案。
常见构造方法：依次处理每条边，维护每个顶点可用的颜色集合，用类似贪心+调整的方法。

重要观察：
颜色用 $0$ 到 $K-1$ 编号（输出时 $+1$）。
因为 $K$ 是 2 的幂，我们可以利用位运算性质。

3. 算法描述

核心想法：
假设当前要加边 $(u,v)$。
令 $c_u$ = 在左点 $u$ 上未使用的最小颜色编号（在 $\{0,\dots,K-1\}$ 中）。
令 $c_v$ = 在右点 $v$ 上未使用的最小颜色编号。

如果 $c_u = c_v$，直接涂这个颜色，完成。

否则 $c_u \neq c_v$，我们尝试把右点 $v$ 的某个邻接边的颜色改成 $c_u$，然后递归调整。
这个过程类似增广路调整，但由于二分图的特殊结构和颜色数是 2 的幂，可以保证在有限步结束且不会冲突。

具体步骤：

1. 在右部点 $v$ 上，我们想用颜色 $c_u$，但 $c_u$ 已被某条边 $(u', v)$ 占用。
2. 那么我们把 $(u', v)$ 改成颜色 $c_v$（这是 $v$ 上未用的颜色）。
3. 然后在左部点 $u'$ 上，颜色 $c_v$ 可能已被 $(u', v')$ 占用，重复这个过程。
4. 这形成一条交替路径：$(u,v)$ 想用 $c_u$，然后 $(u',v)$ 改 $c_v$，然后 $(u',v')$ 想改 $c_u$，... 直到某个右点 $v_t$ 上 $c_u$ 未使用，或某个左点 $u_t$ 上 $c_v$ 未使用，调整结束。

可以证明，因为 $K$ 是 2 的幂，这条路径不会形成环，且一定在有限步内结束。

4. 维护可用颜色

每个顶点维护一个未使用颜色集合，可以用布尔数组或集合，但为了快速找最小未使用颜色，可以用位运算优化：
用一个整数 mask 表示可用的颜色（$K \le 2^{17}$ 最多 $131072$，$\Delta \le M$，但 $K$ 是 2 的幂，最多 $2^{17}$ 种颜色，所以整数位足够表示）。

• 初始 mask = (1<<K)-1，表示所有颜色可用。
• 当使用颜色 $c$，就 mask &= ~(1<<c)。
• 当释放颜色 $c$，就 mask |= (1<<c)。
• 找最小可用颜色：__builtin_ctz(mask)（gcc 内置函数，找最低位 1 的位置）。

5. 复杂度

每条边调整过程可能遍历一条交替路径，长度不超过 $O(K)$，而 $K = O(\Delta)$，最坏 $O(M\Delta)$ 可能过大？
但实际上，由于 $K$ 是 2 的幂，调整路径长度较短，且每个点的可用颜色集合的维护是 $O(1)$，整体可在 $O(M \log \Delta)$ 或 $O(MK)$ 内完成，在数据范围内可接受。

更优实现：使用邻接表存每个点的边（颜色，对端点），并快速修改。

6. 算法步骤

1. 读入图，计算最大度数 $\Delta$。
2. 计算 $K = 2^{\lceil \log_2 \Delta \rceil}$。
3. 初始化：每个左点、右点的可用颜色掩码为 $(1<<K)-1$。
4. 按输入顺序处理每条边 $(u,v)$：
   • 找 $c_u$ = 左点 $u$ 最小可用颜色，$c_v$ = 右点 $v$ 最小可用颜色。
   • 如果 $c_u == c_v$： 涂色，更新两个点的掩码（去掉该颜色）。
   • 否则： 执行调整过程（从右点 $v$ 开始，交替改颜色，直到可以插入 $c_u$ 或 $c_v$）。
5. 输出颜色（记得 $+1$ 因为题目颜色从 1 开始）。

7. 样例验证

样例 1
$L=3,R=3,M=5$
最大度 $\Delta = 2$（点1左度2，点2左度2，右部点度最大2），
$K = 2$。
构造可得方案如样例输出。

样例 2
$L=2,R=4,M=4$
最大度 $\Delta = 3$（左点1度3），
$K = 4$（因为 $4$ 是 $\ge 3$ 的最小 2 的幂）。
所以输出 4 种颜色允许，方案如样例。

总结

这道题的关键点：

1. 利用 Kőnig 定理知道最小颜色数 $C = \Delta$。
2. 放宽到 $2$ 的幂 $K$ 是为了方便构造，利用位运算快速找可用颜色。
3. 用类似增广路调整的方法依次加边并保持颜色不冲突。
4. 由于 $K$ 是 2 的幂，调整路径不会循环，总能结束。

这样就能在 $O(MK)$ 时间内完成构造，满足数据范围要求。