В пошуках нового Вавилону Костя знайшов n шматків карти. Відомо q обмежень, які можна виразити числами a та b. Вони означають, що шматки a та b можна використовувати лише разом.

вхідні данні:

У першому рядку записано числа n та q.(1 ≤ n,q ≤ 3*105) У наступних q рядках записані обмеження.

вихідні данні:

Вивести n чисел, i-йне число - мінімальна кількість шматків карти, щоб можна було використати iий шматок.