Karte

Η Lucija έχει ~n~ κάρτες τοποθετημένες σε μία σειρά. Κάθε κάρτα έχει δύο πλευρές, καθεμία από τις οποίες έχει ένα χρώμα: η μία πλευρά της ~i~-οστής κάρτας έχει χρώμα ~A_i~, ενώ η άλλη έχει χρώμα ~B_i~. Τα χρώματα αναπαρίστανται με θετικούς ακέραιους αριθμούς, ενώ οι δύο πλευρές μιας κάρτας μπορούν να έχουν και το ίδιο χρώμα.

Η Lucija τοποθετεί κάρτες πάνω στο τραπέζι και για κάθε κάρτα επιλέγει ποια πλευρά θα είναι στραμμένη προς τα πάνω. Έτσι, ένα χρώμα από κάθε κάρτα είναι ορατό πάνω στο τραπέζι. Η Lucija θέλει να είναι ορατά όσο το δυνατόν περισσότερα διαφορετικά χρώματα.

Δεν έχει αποφασίσει ακόμα πόσες κάρτες θα τοποθετήσει στο τραπέζι, επομένως θέλετε να υπολογίσετε την απάντηση για κάθε πιθανό αριθμό καρτών. Για κάθε ~k~ από ~1~ έως ~n~, βρείτε τον μέγιστο αριθμό διαφορετικών χρωμάτων που μπορούν να είναι ορατά αν η Lucija τοποθετήσει στο τραπέζι μόνο τις πρώτες ~k~ κάρτες.

Για κάθε τιμή του ~k~, οι πλευρές των καρτών επιλέγονται ανεξάρτητα: η ίδια κάρτα μπορεί να έχει διαφορετική πλευρά στραμμένη προς τα πάνω για διαφορετικές τιμές του ~k~.

Είσοδος

Η πρώτη γραμμή θα περιέχει έναν θετικό ακέραιο ~n~ (~1 \le n \le 100.000~), τον αριθμό των καρτών.

Καθεμία από τις επόμενες ~n~ γραμμές θα περιέχει δύο θετικούς ακέραιους αριθμούς ~A_i~ και ~B_i~ (~1 \le A_i, B_i \le 100.000~), τα χρώματα των δύο πλευρών της ~i~-οστής κάρτας.

Έξοδος

Στη μοναδική γραμμή να εκτυπώσετε ~n~ αριθμούς, διαχωρισμένους με κενά. Ο ~k~-οστός αριθμός πρέπει να είναι ο μέγιστος αριθμός διαφορετικών χρωμάτων που μπορούν να είναι ορατά πάνω στο τραπέζι, αν τοποθετηθούν σε αυτό μόνο οι πρώτες ~k~ κάρτες.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~13~	~n \le 10~
~2~	~17~	Εμφανίζονται συνολικά το πολύ ~5~ διαφορετικά χρώματα σε όλες τις κάρτες.
~3~	~21~	~n \le 1000~
~4~	~19~	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

4
1 2
2 3
1 3
3 3

output

1 2 3 3

Επεξήγηση του πρώτου παραδείγματος:

Με μία κάρτα, είναι ορατό ένα χρώμα. Με τις δύο πρώτες κάρτες, ~(1, 2)~ και ~(2, 3)~, μπορούν να είναι ορατά δύο διαφορετικά χρώματα, για παράδειγμα τα ~1~ και ~2~. Με τις τρεις πρώτες κάρτες, μπορούν να είναι ορατά και τα τρία χρώματα: η πρώτη κάρτα εμφανίζει το χρώμα ~2~, η δεύτερη το χρώμα ~3~ και η τρίτη το χρώμα ~1~. Η τέταρτη κάρτα έχει το χρώμα ~3~ και στις δύο πλευρές της, επομένως δεν μπορεί να προσθέσει κάποιο νέο χρώμα και η απάντηση παραμένει ~3~.

input

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

output

1 1 2 3 4 4

Επεξήγηση του δεύτερου παραδείγματος:

Οι δύο πρώτες κάρτες έχουν το χρώμα ~5~ και στις δύο πλευρές τους, επομένως με αυτές είναι ορατό μόνο ένα χρώμα. Η τρίτη κάρτα εμφανίζει το χρώμα ~7~, ενώ η τέταρτη και η πέμπτη κάρτα εμφανίζουν τα χρώματα ~2~ και ~9~. Η έκτη κάρτα έχει τα ίδια χρώματα με την τέταρτη, επομένως και τα δύο είναι ήδη ορατά και η απάντηση για ~k = 6~ παραμένει ~4~.

input

5
4 4
4 1
2 3
4 2
1 1

output

1 2 3 4 4

Επεξήγηση του τρίτου παραδείγματος:

Για ~k = 3~, η τρίτη κάρτα ~(2, 3)~ μπορεί να εμφανίζει οποιοδήποτε από τα δύο χρώματά της, για παράδειγμα το χρώμα ~2~.

Για ~k = 4~, η πρώτη κάρτα πρέπει να εμφανίζει το χρώμα ~4~, επομένως η δεύτερη κάρτα εμφανίζει το χρώμα ~1~, η τέταρτη κάρτα ~(4, 2)~ εμφανίζει το χρώμα ~2~ και η τρίτη κάρτα εμφανίζει το χρώμα ~3~. Με αυτόν τον τρόπο, είναι ορατά και τα τέσσερα διαφορετικά χρώματα.

Η τρίτη κάρτα έχει διαφορετική πλευρά στραμμένη προς τα πάνω για ~k = 3~ και ~k = 4~, κάτι που επιτρέπεται.