| Входной файл: | input.txt | Ограничение времени: | 1 сек | |
| Выходной файл: | output.txt | Ограничение памяти: | 128 Мб | |
| Максимальный балл: | 11 |
На заводе по сборке матрешек установлен автомат для их упаковки. Принцип его действия таков. Изначально на столе стоит N неупакованных матрешек, пронумерованных от 1 до N, причем вторая матрешка может вкладываться в первую, третья во вторую, четвертая в третью и т.д. матрешка с большим номером может вкладываться в матрешку с меньшим.
За один такт автомат может взять две матрешки и вложить меньшую в большую, причем если в матрешках уже содержаться другие матрешки, то они все вкладываются в самую большую, при этом номера матрешек остаются прежними. Если матрешка уже вложена в другую, то автомат упаковывает ту матрешку в которую она вложена. Программа автомата состоит из чисел N, K и следующих за ними K пар чисел ai, bi — номера матрешек, которые автомат упакует за i-тый такт.
По заданной программе автомата для каждой матрешки определите номер самой большой матрешки в которую она оказалось вложенной после завершения программы.
В выходном файле должно содержаться N чисел — для каждой матрешки номер самой большой матрешки, в которую она оказалось вложенной.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|