A connected graph with \(N\) vertices and \(N\) edges (so-called Namori graph in Japanese) can be considered as an exactly one cycle and trees rooted at vertices on the cycle.

In this problem, it is sufficient to detect a cycle, then determine the root of the tree that each vertex belongs to, which should be a vertex on the cycle. This is because there is a unique path between two vertices belonging to a tree with the same root; otherwise there are two possible path, which are not unique.

There are many ways of implementation; here is an example.

step 1

While there is a vertex of degree \(1\), remove the vertex and the edge incident to it. The remaining vertices form a cycle.

step 2

Perform a DFS from each vertex on the cycle to find the root of the tree that each vertex belongs to.

[sample code (c++)(https://atcoder.jp/contests/abc266/submissions/34320961)]