Padel Prize Pursuit

Υπάρχουν ~N~ συμμετέχοντες με αριθμούς από ~0~ έως ~N - 1~ που διαγωνίζονται σε ένα τουρνουά padel, το οποίο διεξάγεται σε ~M~ ημέρες. Κάθε μέρα διεξάγεται ακριβώς ένας αγώνας. Στο τουρνουά απονέμονται ~M~ μετάλλια, ένα νέο για κάθε αγώνα. Στον αγώνα της ημέρας ~i~ ~(0 \le i \le M - 1)~, οι δύο συμμετέχοντες με αριθμό ~x_i~ και ~y_i~ συμμετέχουν. Στον αγώνα συμβαίνουν τα εξής:

• Ο συμμετέχων ~x_i~ κερδίζει τον συμμετέχοντα ~y_i~
• Ένα νέο μετάλλιο δίνεται στον νικητή ~x_i~
• Όλα τα τρέχοντα μετάλλια του ηττημένου δίνονται στον νικητή.

Την ημέρα ~M~ (την επομένη του τελευταίου αγώνα) πραγματοποιείται η τελετή απονομής των βραβείων. Κατά την τελετή, όλα τα μετάλλια συγκεντρώνονται και στη συνέχεια κάθε μετάλλιο δίνεται στον συμμετέχοντα που κράτησε το μετάλλιο αυτό για μεγαλύτερο χρονικό διάστημα.

Τυπικά, το μετάλλιο ~i~ δίνεται στον συμμετέχοντα που κατείχε το μετάλλιο ~i~ για τις περισσότερες νύχτες (όχι απαραίτητα συνεχόμενες), από την ημέρα ~M~. Εάν δύο ή περισσότεροι συμμετέχοντες έχουν κρατήσει ένα μετάλλιο για τον ίδιο αριθμό νυχτών, το μετάλλιο δίνεται στον συμμετέχοντα με τον μικρότερο δείκτη (index).

Στόχος σας είναι να προσδιορίσετε πόσα μετάλλια απονέμονται σε κάθε συμμετέχοντα κατά την τελετή απονομής των βραβείων.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους ακέραιους αριθμούς ~N~ και ~M~, τον αριθμό των συμμετεχόντων και τον αριθμό των αγώνων.

Στη συνέχεια ακολουθούν ~M~ γραμμές. Η ~i~-οστή από αυτές τις γραμμές περιέχει δύο ακέραιους ~x_i~ και ~y_i~, τους συμμετέχοντες που διαγωνίζονται την ημέρα ~i~, όπου ο συμμετέχων ~x_i~ κερδίζει τον συμμετέχοντα ~y_i~.

Έξοδος

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

Περιορισμοί

• ~2 \le N \le 200 000~
• ~1 \le M \le 200 000~
• ~0 \le x, y \le N - 1~ και ~x \ne y~ (για όλα τα ~0 \le i \le M - 1~).

Η λύση σας θα δοκιμαστεί σε ένα σύνολο ομάδων δοκιμών, καθεμία από τις οποίες αξίζει έναν αριθμό βαθμών. Κάθε ομάδα δοκιμών περιέχει ένα σύνολο δοκιμαστικών περιπτώσεων. Για να λάβετε τους πόντους για μια ομάδα δοκιμών πρέπει να λύσετε όλες τις δοκιμαστικές περιπτώσεις της ομάδας.

Η λύση σας θα δοκιμαστεί σε ένα σύνολο ομάδων δοκιμών, καθεμία από τις οποίες αξίζει έναν αριθμό βαθμών. Κάθε ομάδα δοκιμών περιέχει ένα σύνολο περιπτώσεων δοκιμών. Για να λάβετε τους πόντους για μια ομάδα δοκιμών πρέπει να λύσετε όλες τις περιπτώσεις δοκιμών στην ομάδα δοκιμών.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	12	~N = 2~
2	16	~N, M \le 2000~
3	15	Ο νικητής του ~i~-οστού αγώνα συμμετέχει στον (~i + 1~)-οστό αγώνα, για κάθε ~i~, έτσι ώστε ~0 \le i \le M - 2~.
4	20	Τη στιγμή του ~i~-οστού αγώνα, ο ~x_i~ έχει τουλάχιστον τόσα μετάλλια όσα και ο ~y_i~, για κάθε ~i~ έτσι ώστε ~0~ \le i \le M - 1~.
5	22	Μόλις ένας συμμετέχων χάσει, δεν ξαναπαίρνει μέρος σε αγώνα.
6	15	Κανένας επιπλέον περιορισμός.

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

input

3 4
0 1
2 1
1 0
2 1

output

1 1 2

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

Για την πρώτη περίπτωση δοκιμής, η ακόλουθη εικόνα δείχνει ποιος είχε ποια μετάλλια καθ' όλη τη διάρκεια του τουρνουά. Όταν ο συμμετέχων ~1~ χάνει την ~3~η ημέρα, όλα τα μετάλλιά του δίνονται στον συμμετέχοντα ~2~.

///ΕΙΚΟΝΑ///

input

3 7
0 1
0 2
2 0
0 1
1 0
2 0
0 2

output

2 2 3

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

Το δεύτερο παράδειγμα μπορείτε να το δείτε παρακάτω.

///ΕΙΚΟΝΑ///

Μετά την τελετή απονομής των βραβείων, στον συμμετέχοντα ~0~ δίνονται τα μετάλλια ~5~ και ~6~, στον συμμετέχοντα ~1~ δίνονται τα μετάλλια ~3~ και ~4~ και στον συμμετέχοντα ~2~ δίνονται τα μετάλλια ~0~, ~1~ και ~2~.

input

6 10
2 5
3 0
4 2
0 1
4 3
2 4
0 3
0 2
5 2
5 0

output

5 0 1 1 1 2