P17823 [COCI 2026/2027 #1] Karte

Lucija has $n$ cards arranged in a row. Every card has **two sides** with one color on each side: one side of the $i$-th card has color $A_i$, and the other side has color $B_i$. Colors are labelled with positive integers, and the two sides of a card may also have **the same color**. Lucija puts cards on the table, and for each card she chooses **which side faces up**. One color from each card is then visible on the table. Lucija wants **as many different colors as possible** to be visible. She has not yet decided how many cards to put on the table, so you want to know the answer for every possible number. For each $k$ from $1$ to $n$, find the largest number of different colors that can be visible if Lucija puts **only the first $k$ cards** on the table. For each $k$, the sides of the cards are chosen **independently**: the same card may face different sides up for different values of $k$.

The first line contains a positive integer $n$ ($1\le n\le 100\,000$), the number of cards. The $i$-th of the following $n$ lines contains positive integers $A_i$ and $B_i$ ($1\le A_i,B_i\le 100\,000$), the colors on the two sides of the $i$-th card.

In the only line, output $n$ numbers separated by spaces. The $k$-th number should be the largest number of different colors that can be visible on the table if only the first $k$ cards are on it.

#### Clarification of the first example With one card, one color is visible. With the first two cards, $(1,2)$ and $(2,3)$, two different colors can be visible, for example $1$ and $2$. With the first three cards, all three colors can be visible: the first card shows color $2$, the second color $3$, and the third color $1$. The fourth card has color $3$ on both sides, so it cannot add a new color, and the answer stays $3$. #### Clarification of the second example The first two cards have color $5$ on both sides, so only one color is visible with them. The third card shows color $7$, and the fourth and fifth cards show colors $2$ and $9$. The sixth card has the same colors as the fourth one, and both are already visible, so the answer for $k=6$ is also $4$. #### Clarification of the third example For $k=3$, the third card $(2,3)$ may show either of its colors, for example color $2$. For $k=4$, the first card has to show color $4$, so the second card shows color $1$, the fourth card $(4,2)$ shows color $2$, and the third card shows color $3$. This way all four colors are visible. The third card faces different sides up for $k=3$ and $k=4$, which is allowed. #### Scoring | Subtask | Points | Constraints | | --- | --- | --- | | 1 | 13 | $n\le 10$. | | 2 | 17 | At most $5$ different colors appear on all the cards in total. | | 3 | 21 | $n\le 1000$. | | 4 | 19 | No additional constraints. |