Задача №114799. Стринг-арт
Начинающие художники-предприниматели Даня и Саша создают картины в технике стринг-арт. Картина в этой технике представляет собой \(n\) гвоздиков, вбитых в специальную доску, \(m\) пар которых соединены нитками. Чтобы картина выглядела как единое целое, от любого гвоздика до любого другого можно добраться по ниткам.
Даня и Саша хотят производить наборы для стринг-арта, которые позволят покупателю самому создать картину по инструкции. К сожалению, они выяснили, что если просто отправить клиенту \(n\) гвоздиков, \(m\) ниток и картинку, которую требуется получить, многие покупатели не справляются. Поэтому они решили продавать заготовки для картин.
Заготовка для картины состоит из \(m\) ниточек, соединяющих бусинки. Ниточки соединяют бусинки таким образом, что от любой бусинки до любой другой существует ровно один путь по ниточкам. Каждая бусинка покрашена в определенный цвет. Чтобы получить из заготовки картину, покупатель раскладывает заготовку на доске, так чтобы бусинки одного цвета лежали в одной точке, и затем прибивает их гвоздиками. В результате должна получиться исходно задуманная художниками картина.
Даня и Саша разработали очень красивую картину, теперь они хотят сделать для нее заготовку. Помогите им!
Первая строка ввода содержит два натуральных числа \(n\) и \(m\) (\(1 \leq n \leq 10^5\), \(1 \leq m \leq 2 \cdot 10^5\)) — число гвоздиков на картине и число ниточек на ней.
Каждая из последующих \(m\) строк содержит по два натуральных числа \(u\) и \(v\) (\(1 \leq u, v \leq n\)) — номера гвоздиков соединённых соответствующей ниточкой. Никакая пара гвоздиков не соединена более, чем одной ниточкой, и никакой гвоздик не соединён ниточкой сам с собой. От любого гвоздика до любого можно добраться по ниточкам.
Выведите описание заготовки для картины.
Первая строка должна содержать одно натуральное числа \(c\) — количество бусинок в заготовке.
Вторая строка должна содержать \(c\) натуральных чисел \(a_1, a_2, \ldots, a_c\) (\(1 \leq a_i \leq n\)) — цвета бусинок, при этом бусинки цвета \(k\) будут прибиты к доске \(k\)-м гвоздиком в описанной во вводе картине.
Каждая из последующих \(m\) строк должна содержать два натуральных числа — номера бусинок, соединённых очередной ниточкой. От каждой бусинки до каждой должен быть ровно один путь по ниточкам.
Если подходящих заготовок несколько, выведите описание любой из них.
3 2 1 2 2 3
3 1 2 3 2 3 1 2
5 5 1 2 2 3 1 4 3 4 4 5
6 1 2 3 4 1 5 4 5 4 6 3 4 2 3 1 2