A connected undirected graph is given by its edges. Does it have an Euler circuit (a closed walk using every edge exactly once), an Euler path (using every edge once, but not closed), or neither?
Input
The first line has n and m (2 ≤ n ≤ 100 vertices numbered 1 to n, 1 ≤ m ≤ 500 edges). Each of the next m lines has an edge u v (u ≠ v). Two vertices may be joined by more than one edge (like Königsberg's bridges).
Output
circuit, or path u v where u < v are the two vertices of odd degree, or none.
Examples
Example 1 · Input
4 4 1 2 2 3 3 4 4 1
Expected output
circuit
Example 2 · Input
4 7 1 2 1 2 3 2 3 2 1 4 3 4 2 4
Expected output
none
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Count each vertex's degree: each edge adds 1 to both ends.
Hint 2
Collect the vertices with odd degree.
Hint 3
0 odd vertices: a circuit; 2: a path between them; otherwise none.
Solution
Show one correct solution (try it yourself first)
n, m = map(int, input().split())
degree = [0] * (n + 1)
for _ in range(m):
u, v = map(int, input().split())
degree[u] += 1
degree[v] += 1
odd = [v for v in range(1, n + 1) if degree[v] % 2 == 1]
if not odd:
print("circuit")
elif len(odd) == 2:
print("path", odd[0], odd[1])
else:
print("none")