题目描述

Lucija 有排成一行的 $n$ 张卡片。每张卡片都有两个面，每个面各有一种颜色：第 $i$ 张卡片的一面颜色为 $A_i$，另一面颜色为 $B_i$。颜色用正整数表示，同一张卡片的两面也可能是相同的颜色。

Lucija 将卡片放到桌上，并为每张卡片选择哪一面朝上。这样，每张卡片都有一种颜色在桌上可见。Lucija 希望可见的不同颜色数量尽可能多。

她还没有决定要在桌上放多少张卡片，所以你想知道每一种可能数量对应的答案。对于从 $1$ 到 $n$ 的每个 $k$，求出当 Lucija 仅将前 $k$ 张卡片放到桌上时，最多能看见多少种不同的颜色。

对于不同的 $k$，各张卡片朝上的一面可以独立选择：同一张卡片在不同的 $k$ 下，可以选择不同的一面朝上。

输入格式

第一行包含一个正整数 $n$（$1\le n\le 100\,000$），表示卡片数量。

接下来 $n$ 行中的第 $i$ 行包含两个正整数 $A_i$ 和 $B_i$（$1\le A_i,B_i\le 100\,000$），表示第 $i$ 张卡片两个面的颜色。

输出格式

输出一行，包含 $n$ 个以空格分隔的数。第 $k$ 个数表示当桌上仅有前 $k$ 张卡片时，最多可以看见多少种不同的颜色。

4
1 2
2 3
1 3
3 3

1 2 3 3

6
5 5
5 5
7 5
2 9
9 2
2 9

1 1 2 3 4 4

5
4 4
4 1
2 3
4 2
1 1

1 2 3 4 4

提示

样例 1 解释

只有一张卡片时，可以看见一种颜色。只有前两张卡片 $(1,2)$ 和 $(2,3)$ 时，可以看见两种不同的颜色，例如 $1$ 和 $2$。只有前三张卡片时，可以让三种颜色全部可见：第一张卡片显示颜色 $2$，第二张显示颜色 $3$，第三张显示颜色 $1$。第四张卡片的两面均为颜色 $3$，因此无法增加一种新颜色，答案仍为 $3$。

样例 2 解释

前两张卡片的两面均为颜色 $5$，因此只使用它们时只能看见一种颜色。第三张卡片显示颜色 $7$，第四张和第五张卡片分别显示颜色 $2$ 和 $9$。第六张卡片的颜色与第四张相同，而这两种颜色都已经可见，因此 $k=6$ 时的答案也为 $4$。

样例 3 解释

当 $k=3$ 时，第三张卡片 $(2,3)$ 可以显示其中任意一种颜色，例如颜色 $2$。当 $k=4$ 时，第一张卡片只能显示颜色 $4$，因此让第二张显示颜色 $1$，第四张卡片 $(4,2)$ 显示颜色 $2$，第三张显示颜色 $3$。这样，四种颜色全部可见。第三张卡片在 $k=3$ 和 $k=4$ 时朝上的面不同，这是允许的。

评分标准