Magic Forest Energy Assignment

In the enchanted forest, every tree is connected by magical pathways. The wise wizards want to assign energies to the trees so that each pathway conveys the same amount of magical energy. Formally, consider each tree as a vertex and each pathway as an edge. A valid energy assignment is possible if and only if for every vertex v, the degree of v satisfies \(\deg(v) \equiv 0 \; (\bmod\;2)\). Your task is to determine whether such a uniform energy assignment exists.

Input consists of multiple test cases. For each test case, you are given the number of trees and the number of pathways, followed by a list of connections between trees. The input terminates with a line containing "0 0" which should not be processed.

inputFormat

The input is read from standard input (stdin) and consists of multiple test cases. Each test case begins with a line containing two integers n and m, where n is the number of trees and m is the number of magical pathways. Following this, there are m lines, each containing two integers representing a pathway between two trees. The input terminates with a line "0 0" which should not be processed.

outputFormat

For each test case, output a single line to standard output (stdout) containing either "Possible" if it is possible to assign energies such that every pathway carries the same magical energy, or "Impossible" otherwise.

4 4
1 2
2 3
3 4
4 1
0 0

Possible