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

Вхідні данні

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

Вихідні данні

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