CF1439E.Cheat and Win

Let's consider a $(10^9+1) \times (10^9+1)$ field. The rows are numbered with integers from $0$ to $10^9$ and the columns are numbered with integers from $0$ to $10^9$. Let's define as $(x, y)$ the cell located in the $x$-th row and $y$-th column.

Let's call a cell $(x, y)$ good if $x \& y = 0$, there $\&$ is the bitwise and operation.

Let's build a graph where vertices will be all good cells of the field and we will make an edge between all pairs of adjacent by side good cells. It can be proved that this graph will be a tree — connected graph without cycles. Let's hang this tree on vertex $(0, 0)$, so we will have a rooted tree with root $(0, 0)$.

Two players will play the game. Initially, some good cells are black and others are white. Each player on his turn chooses a black good cell and a subset of its ancestors (possibly empty) and inverts their colors (from white to black and vice versa). The player who can't move (because all good cells are white) loses. It can be proved that the game is always finite.

Initially, all cells are white. You are given $m$ pairs of cells. For each pair color all cells in a simple path between them as black. Note that we do not invert their colors, we paint them black.

Sohrab and Mashtali are going to play this game. Sohrab is the first player and Mashtali is the second.

Mashtali wants to win and decided to cheat. He can make the following operation multiple times before the game starts: choose a cell and invert colors of all vertices on the path between it and the root of the tree.

Mammad who was watching them wondered: "what is the minimum number of operations Mashtali should do to have a winning strategy?".

Find the answer to this question for the initial painting of the tree. It can be proved that at least one possible way to cheat always exists.

我们考虑一个 $(10^9+1) \times (10^9+1)$ 的方格。行编号为从 $0$ 到 $10^9$ 的整数，列编号也为从 $0$ 到 $10^9$ 的整数。记 $(x, y)$ 为位于第 $x$ 行、第 $y$ 列的格子。

若满足 $x \& y = 0$，则称格子 $(x, y)$ 是好格子，其中 $\&$ 表示按位与运算。

我们构造一个图：其顶点集为所有好格子；对任意两个边相邻（即共享一条边）的好格子之间连一条无向边。可以证明，该图是一棵树——即连通且无环的图。我们将这棵树以顶点 $(0, 0)$ 为根悬挂起来，从而得到一棵以 $(0, 0)$ 为根的有根树。

两名玩家将进行如下博弈：初始时，某些好格子为黑色，其余为白色。每一轮中，当前玩家选择一个黑色的好格子，并选择其任意一个祖先集合（可以为空集），然后将这些格子的颜色全部翻转（白变黑，黑变白）。无法操作者（即所有好格子均为白色时）判负。可以证明，该博弈总是有限的。

初始时，所有格子均为白色。现给出 $m$ 对格子。对每一对格子，将它们之间简单路径上的所有格子染成黑色。（注意：此处不是翻转颜色，而是直接涂黑。）

Sohrab 和 Mashtali 将进行这场博弈，Sohrab 先手，Mashtali 后手。

Mashtali 想获胜，因此决定作弊。他在游戏开始前可执行以下操作任意多次：任选一个格子，并将该格子到树根（即 $(0, 0)$）路径上所有顶点的颜色全部翻转。

在一旁观察的 Mammad 心生疑惑：“Mashtali 至少需要执行多少次上述作弊操作，才能保证自己拥有必胜策略？”

请针对给定的初始染色方案，回答这一问题。可以证明，总存在至少一种可行的作弊方式。

The first line contains one integer $m$ ($1 \leq m \leq 10^5$).

Each of the next $m$ lines contains four integers $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ ($0 \leq x_i, y_i \leq 10^9$, $x_i \& y_i = 0$). You should color all cells on the path between vertices $(x_1, y_1)$ and $(x_2, y_2)$ as black.

第一行包含一个整数 $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)$ 之间路径上的所有格子涂成黑色。

Print a single integer — the minimum number of cheating operations the second player can do.

输出一个整数——第二位玩家所需的最少作弊操作次数。

In the first test, you can make one cheating operation with the root of the tree. After that, the second player can win because he can use a symmetric strategy.

In the second test, you can make cheating operations with cells $(0, 2), (0, 0), (3, 4)$.

In the third test, the second player already has the winning strategy and doesn't need to make any cheating operations.

在第一个测试中，你可以对树的根节点执行一次作弊操作。此后，第二名玩家可以获胜，因为他可以采用对称策略。

在第二个测试中，你可以对格子 $(0, 2), (0, 0), (3, 4)$ 执行作弊操作。

在第三个测试中，第二名玩家已拥有必胜策略，无需执行任何作弊操作。