给你 $$$n$$$ 二进制堆,其中第 $$$i$$$ 个由顶部的 $$$a_i$$$ 零和底部的 $$$b_i$$$ 组成。
在一次操作中,您可以获取 顶部元素 任何一堆并将其移动到任何一堆中的任何位置,包括它被取出的那堆。
第一个示例测试用例的解决方案。 输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 堆的数量。
接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含四个整数 $$$a_i$$$、$$$b_i$$$、$$$c_i$$$、$$$d_i$$$ ($$$0 \leq a_i, b_i, c_i, d_i \leq 10^9$$$) — 原始值和目标值第 $$$i$$$ 堆的状态。
保证存在将桩转换为目标状态的一系列操作。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——达到目标状态所需的最少操作数。
示例
输入复制
321 3 1 21 1 1 232 0 2 20 1 1 01 1 0 031 2 1 23 4 3 40 0 0 0
输出复制
2 3 0
注意
第一个测试用例的解决方案如语句所示。
在第二个测试用例中,最佳解决方案是执行以下操作:
在第三个测试用例中,所有桩都已处于目标状态。