P17823 [COCI 2026/2027 #1] 卡片 / Karte

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$ 张卡片时，最多可以看见多少种不同的颜色。

### 样例 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$ 时朝上的面不同，这是允许的。 ### 评分标准 | 子任务 | 分值 | 附加限制 | | --- | --- | --- | | 1 | 13 | $n\le 10$。 | | 2 | 17 | 所有卡片上总共至多出现 $5$ 种不同的颜色。 | | 3 | 21 | $n\le 1000$。 | | 4 | 19 | 无附加限制。 |