29380번 - Гарри Поттер и железная дорога 스페셜 저지다국어

Гарри, возглавив подразделения мракоборцев, решил защитить железные дороги от злой магии. Всего в мире волшебников $n$ железнодорожных станций и $m$ железных дорог, соединяющих эти станции. Каждая дорога соединяет две различные станции, причем станции могут быть соединены более чем одной дорогой. По каждой железной дороге поезда ходят в обе стороны. Также известно, что между любыми двумя станциями существует путь, состоящий из железных дорог.

У Гарри в запасе $m$ новых защитных заклинаний, пронумерованных целыми числами от $1$ до $m$. Каждое заклинание накладывается на какую-то железную дорогу. Гарри не может использовать одно и то же заклинание для защиты более чем одной железной дороги.

Помимо защиты железных дорог, Гарри хочет, чтобы те же заклинания охраняли и станции. Станция находится под охраной, если наибольший общий делитель номеров заклинаний, защищающих железные дороги, соединяющие эту станцию с остальными, равен единице.

Помогите Гарри защитить все железные дороги так, чтобы каждая станция была под охраной.

В первой строке входного файла находится целое число $n$ ($1 \le n \le 50{\,}000$) --- количество железнодорожных станций и число $m$ ($n-1 \le m \le 150{\,}000$) --- количество железных дорог. Каждая из следующих $m$ строк содержит по два целых числа: $a_i$ и $b_i$ ($1 \le a_i,b_i \le n, a_i \ne b_i $) --- номера станций, соединенных этой железной дорогой.

Выведите <<IMPOSSIBLE>>, если невозможно защитить все дороги так, чтобы каждая станция была под охраной. В противном случае выведите $m$ чисел по одному в строке, $i$-я строка должна содержать номер заклинания, которое защищает железную дорогу, описанную в $i+1$-й строке входного файла.