Hamiltonian Cycle - Baton Passing

Given an undirected graph with $$n$$ vertices and $$m$$ edges, determine whether there exists a Hamiltonian cycle. In other words, check if it is possible to form a cycle that visits every vertex exactly once and returns to the starting vertex.

Imagine a scenario where each vertex represents a student and an edge represents a friendship. The problem is to decide if it is possible for the students to pass a baton such that each student passes it exactly once before it returns to the starting student.

inputFormat

The input is given via standard input (stdin). The first line contains two integers $$n$$ and $$m$$, where $$n$$ is the number of vertices and $$m$$ is the number of edges. Each of the following $$m$$ lines contains two integers $$u$$ and $$v$$ which describe an undirected edge between vertices $$u$$ and $$v$$.

outputFormat

Output a single line to standard output (stdout): "possible" if a Hamiltonian cycle exists, otherwise "impossible".## sample

4 4
1 2
2 3
3 4
4 1

possible