CF1439E Cheat and Win

我们考虑一个 $ (10^9+1) \times (10^9+1) $ 的网格。行编号为 $ 0 $ 到 $ 10^9 $ 的整数，列编号也为 $ 0 $ 到 $ 10^9 $ 的整数。我们用 $ (x, y) $ 表示第 $ x $ 行第 $ y $ 列的格子。 如果 $ x \& y = 0 $，则称格子 $ (x, y) $ 是“好格子”，其中 $ \& $ 表示[按位与](https://en.wikipedia.org/wiki/Bitwise_operation#AND)运算。 我们以所有好格子为顶点构建一张图，并在所有相邻的好格子之间连边。可以证明，这张图是一棵树——即连通且无环。我们将这棵树以 $ (0, 0) $ 为根节点，得到一棵有根树。 有两名玩家进行游戏。最初，部分好格子为黑色，其余为白色。每一回合，玩家选择一个黑色好格子及其若干祖先（可以为空），并将这些格子的颜色反转（白变黑，黑变白）。如果某一玩家无法操作（即所有好格子均为白色），则判负。可以证明，这个游戏一定会在有限步内结束。 最初，所有格子都是白色。你会得到 $ m $ 对格子，对于每一对格子，将它们之间的简单路径上的所有格子染成黑色。注意，这里是直接染黑，不是反转颜色。 Sohrab 和 Mashtali 将要进行这场游戏。Sohrab 先手，Mashtali 后手。 Mashtali 想要获胜，于是决定作弊。他可以在游戏开始前多次进行如下操作：选择一个格子，将它到树根的路径上的所有顶点颜色反转。 Mammad 作为观众，产生了疑问：“Mashtali 至少需要做多少次作弊操作，才能保证自己有必胜策略？” 请你针对初始染色状态，求出 Mashtali 至少需要做多少次作弊操作。可以证明，至少存在一种作弊方案使得 Mashtali 有必胜策略。

第一行包含一个整数 $ m $（$ 1 \leq m \leq 10^5 $）。 接下来 $ m $ 行，每行包含四个整数 $ x_{1}, y_{1}, x_{2}, y_{2} $（$ 0 \leq x_i, y_i \leq 10^9 $，且 $ x_i \& y_i = 0 $）。你需要将每对顶点 $ (x_1, y_1) $ 和 $ (x_2, y_2) $ 之间的路径上的所有格子染成黑色。

输出一个整数，表示 Mashtali 至少需要做多少次作弊操作。

在第一个样例中，你可以对树根进行一次作弊操作。之后，后手玩家可以采用对称策略获胜。 在第二个样例中，你可以对 $(0, 2), (0, 0), (3, 4)$ 这三个格子分别进行作弊操作。 在第三个样例中，后手玩家已经有必胜策略，无需再进行任何作弊操作。 由 ChatGPT 4.1 翻译