Finding a Valid Continuous Path

You are given N viewpoints and M undirected connections between them. Your task is to determine whether there exists a valid continuous path that visits every viewpoint exactly once, where each consecutive pair of viewpoints in the path is directly connected by an edge. Such a path is possible if and only if the graph formed by the viewpoints and connections is a simple path. In other words, the graph should have exactly two endpoints (vertices with degree 1) and all other vertices should have degree 2. If a valid path exists, output the order of the viewpoints (as space-separated values). Otherwise, output "No valid path".

Mathematically, if we denote the number of viewpoints as $N$ and the number of connections as $M$, then a valid path exists if and only if:

[ \text{There are exactly two vertices } v \text{ such that } degree(v)=1 \quad \text{and} \quad (N-2) \text{ vertices with } degree(v)=2. ]

inputFormat

The first line contains two integers N and M separated by a space, where N is the number of viewpoints and M is the number of connections. Each of the following M lines contains two integers u and v indicating that there is an undirected connection between viewpoints u and v.

outputFormat

If a valid path exists, output a single line with the viewpoints in the order they are visited (space-separated). Otherwise, print "No valid path".

5 4
1 2
2 3
3 4
4 5

1 2 3 4 5