В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ — количество комнат и переходов соответственно ($$$1 \le n \le 2 \cdot 10^5$$$; $$$n - 1 \le m \le \left\lfloor \frac{3(n - 1)}{2} \right\rfloor$$$). Комнаты пронумерованы от $$$1$$$ до $$$n$$$.

В каждой из следующих $$$m$$$ строк заданы два целых числа $$$u_i$$$ и $$$v_i$$$ — номера комнат, соединённых переходом ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$). По каждому переходу можно пройти в обоих направлениях.

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

Также гарантируется, что каждое ребро графа принадлежит не более чем одному вершинно простому циклу.

Напомним, что вершинно простой цикл — это замкнутый путь, в котором все вершины, кроме совпадающих начальной и конечной, различны. Разные простые циклы могут иметь общие вершины.