#216578. [EGOI 2026] 狐狸家族 / Fox Families

最近，阿尔卑斯山脉（Alps）的一大片区域被划定为自然保护区。

起初，保护区内并没有狐狸。然而，多亏了持续的保护措施，保护区内的狐狸种群数量逐日恢复。每天都有一只新的狐狸到来。

生物学家 Simona 正在观察这恢复过程，她对狐狸在任何时间点形成的独特家族数量很感兴趣。Simona 知道每只狐狸 都有一个狩猎领地，可以用线段 表示，其中 。这些领地可能会重叠，甚至相互包含。

根据她的研究，Simona 知道如果两只狐狸 和 的狩猎领地中，有一个领地嵌套在另一个领地内（即 或 ），那么它们就是直接亲属关系。

两只狐狸属于同一个家族，当且仅当它们要么是直接亲属，要么通过一系列直接亲属的狐狸链相连。正式地说，两只狐狸 和 属于同一个家族，当且仅当存在一个狐狸序列 ，使得 且 ，并且对于每个 ， 与 是直属关系。

狐狸 () 在第 天到达，并从那时起一直留在保护区内，永久保持相同的狩猎领地 。每只狐狸的到来可能会也可能不会改变家族关系。每天过后，Simona 都想知道狐狸 到达后，现存的狐狸家族数量。

输入的第一行包含一个整数 ，表示天数。接下来的 行，每行包含两个整数 和 ，描述狐狸 的狩猎领地。

输出 行。第 行（对于 ）应包含一个整数，表示狐狸 到达后存在的狐狸家族数量。

样例输入 1

4
1 4
3 6
3 4
6 7

样例输出 1

1
2
1
2

样例输入 2

6
0 1
1 2
2 3
3 4
4 5
2 4

样例输出 2

1
2
3
4
5
4

样例输入 3

5
0 5
1 4
2 7
3 6
4 5

样例输出 3

1
1
2
2
1

样例解释

第一个样例满足子任务 1、2 和 5 的限制。第二个样例满足子任务 1、2、3 和 5 的限制。第三个样例满足子任务 1、2、4 和 5 的限制。

第一个样例。 第一只狐狸到达后，有一个家族。第二只狐狸到达后，有两个家族，因为 和 重叠但没有任何一个领地包含另一个。然后，领地为 的狐狸到达：它被 和 包含，所以这两个家族合并，家族数量现在为 。最后，领地为 的狐狸没有包含任何之前的领地，也没有被包含在它们之中，因此它形成了一个新的家族，家族数量现在为 。

:::align{center} :::

约束条件

• .
• .
• 对于任意两个领地， 不会重复出现。

评分方式

你的程序将在分成若干子任务的测试数据上进行测试。要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。

• 子任务 [ 分]: 样例。
• 子任务 [ 分]: 。
• 子任务 [ 分]: 。
• 子任务 [ 分]: 。
• 子任务 [ 分]: 。
• 子任务 [ 分]: 没有额外的约束条件。