Задача S. Матрешки

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:128 Мб
Максимальный балл:11  

Условие

На заводе по сборке матрешек установлен автомат для их упаковки. Принцип его действия таков. Изначально на столе стоит N неупакованных матрешек, пронумерованных от 1 до N, причем вторая матрешка может вкладываться в первую, третья во вторую, четвертая в третью и т.д. матрешка с большим номером может вкладываться в матрешку с меньшим.

За один такт автомат может взять две матрешки и вложить меньшую в большую, причем если в матрешках уже содержаться другие матрешки, то они все вкладываются в самую большую, при этом номера матрешек остаются прежними. Если матрешка уже вложена в другую, то автомат упаковывает ту матрешку в которую она вложена. Программа автомата состоит из чисел N, K и следующих за ними K пар чисел ai, bi — номера матрешек, которые автомат упакует за i-тый такт.

По заданной программе автомата для каждой матрешки определите номер самой большой матрешки в которую она оказалось вложенной после завершения программы.

Формат входного файла

Во входном файле содержатся два числа NиK, в следующих K строках находится программа автомата.

Формат выходного файла

В выходном файле должно содержаться N чисел — для каждой матрешки номер самой большой матрешки, в которую она оказалось вложенной.

Ограничения

0 ≤ N, K ≤ 100000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3
1 2
2 3
1 3
1 1 1 4

0.024s 0.005s 15