让我们考虑一个 $$$(10^9+1) \times (10^9+1)$$$ 字段。行用从 $$$0$$$ 到 $$$10^9$$$ 的整数进行编号,列用从 $$$0$$$ 到 $$$10^9$$$ 的整数进行编号。我们将位于 $$$x$$$ 行和 $$$y$$$ 列的单元格定义为 $$$(x, y)$$$。
我们称一个单元格为$$$(x, y)$$$ 好,如果$$$x \& y = 0$$$,其中$$$\&$$$ 是按位与运算。
让我们构建一个图,其中顶点将是场中的所有好单元,并且我们将在所有相邻的好单元对之间创建一条边。可以证明该图是一个无环的树连通图。让我们把这棵树挂在顶点 $$$(0, 0)$$$ 上,这样我们就会有一个根为 $$$(0, 0)$$$ 的有根树。
两名玩家将玩游戏。最初,一些好的细胞是黑色的,另一些是白色的。每个玩家轮流选择一个黑色的好单元格及其祖先的子集(可能是空的)并反转它们的颜色(从白色到黑色,反之亦然)。不能移动的玩家(因为所有好的单元格都是白色的)就输了。可以证明博弈总是有限的。
最初,所有单元格都是白色的。您将获得 $$$m$$$ 单元格对。对于每一对,将它们之间的简单路径中的所有单元格着色为黑色。请注意,我们不会反转它们的颜色,而是将它们涂成黑色。
Sohrab 和 Mashtali 将玩这个游戏。索拉博(Sohrab)是第一位玩家,马什塔利(Mashtali)是第二位。
Mashtali 想要获胜并决定作弊。他可以在游戏开始之前多次进行以下操作:选择一个单元格并反转它与树根之间的路径上的所有顶点的颜色。
看着他们的 Mammad 想知道:“为了制定获胜策略,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)$$$ 之间的路径上的所有单元格着色为黑色。
输出
打印一个整数——第二个玩家可以进行的最少作弊操作数。
示例
输入 #1
1 7 0 0 7
输出 #1
1
输入 #2
3 1 2 3 4 3 4 1 2 2 1 3 4
输出 #2
3
输入 #3
2 0 1 0 8 1 0 8 0
输出 #3
0
注意
在第一个测试中,您可以对树的根进行一次作弊操作。之后,第二个玩家可以获胜,因为他可以使用对称策略。
在第二个测试中,您可以对单元格$$$(0, 2), (0, 0), (3, 4)$$$进行作弊操作。
在第三次测试中,第二名玩家已经有了获胜策略,不需要进行任何作弊操作。