Problem Description

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$.

Input Format

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.

Output Format

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.

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

Hint

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