Задача №111581. Гарри Поттер и железная дорога
Гарри, возглавив подразделения мракоборцев, решил защитить железные дороги от злой магии. Всего в мире волшебников \(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\)-й строке входного файла.
5 6 1 5 1 4 5 4 4 1 3 2 3 4
4 3 5 6 1 2