Максим Витальевич решил разобраться в теории графов. Он изучил некоторую теорию касательно связных неориентированных графов, однако здесь у Максима Витальевича возникли трудности.

Среди всех видов связных неориентированных графов, Максим Витальевич подробно разобрался только в деревьях. Напомним, что дерево — это связный граф, не содержащий циклов, состоящий из $$$n$$$ вершин и $$$n - 1$$$ ребер. Другие виды графов вызывают некоторые трудности, так как в них могут быть циклы, либо они могут быть несвязными.

Чтобы разобраться с более сложными видами графов, Максим Витальевич решил их представлять в виде объединения набора деревьев. Для простоты он решил ограничиться только двумя деревьями. Для того, чтобы представить граф из $$$n$$$ вершин в виде объединения двух деревьев, Максим Витальевич раскрасил каждое ребро в один из трех цветов. Далее он построил первое дерево из $$$n$$$ вершин, используя ребра, раскрашенные цветами $$$1$$$ и $$$3$$$, а второе дерево из $$$n$$$ вершин — используя ребра, раскрашенные цветами $$$2$$$ и $$$3$$$. Таким образом, если объединить два дерева, то получится исходный граф, так как каждое ребро принадлежит как минимум одному дереву.

На этом сложности не закончились. Максим Витальевич заметил, что некоторые графы довольно сложно раскрасить так, чтобы в результате получалось два дерева с исходным набором вершин. Поэтому Максим Витальевич обратился к вам за помощью.

Помогите Максиму Витальевичу раскрасить $$$m$$$ ребр графа из $$$n$$$ вершин в три цвета так, чтобы его можно было представить в виде двух деревьев, каждое из которых состоит из $$$n$$$ вершин.