Большая подсказка — так как граф связный, и в нем N вершин и N ребер, то это цикл, к которому подвешено несколько деревьев.

Думаю, это поможет в дальнейших рассуждениях. Нужно лишь рассмотреть несколько случаев.