Безопасное путешествие
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды во сне Рик увидел вселенную, состоящую из нескольких планет. Между некоторыми из них существуют пути (не более одного между двумя планетами), каждым из которых можно воспользоваться для перемещения между двумя определенными планетами в любую сторону. Рик понял, что хочет начать свое путешествие на случайной планете p, затем воспользоваться случайным путем перемещения на другую планету, и так далее. При этом Рику не интересно посещать какую-либо планету дважды, поэтому на каждом шаге следующая планета будет выбираться только среди непосещенных. Когда на очередном шаге Рик не сможет переместиться на непосещенную планету, он переместится на исходную планету p (если, конечно, существует путь на планету p с текущей планеты).

Рик сразу заметил, что вселенная является безопасной, то есть при такой стратегии путешествия он всегда побывает на всех n планетах, и закончит свое путешествие на исходной планете p.

К сожалению, после пробуждения Рик не смог вспомнить, между какими планетами вселенной существуют пути. Однако, он помнит, что во вселенной было n планет и m путей между ними.

Помогите Рику придумать любую безопасную вселенную, состоящую из ровно n планет и ровно m путей между ними, или определите, что это невозможно.

Входные данные

Первая и единственная строка входных данных содержит два натуральных числа n и m — количества планет и путей перемещения между ними (1 < n ≤ 13, ).

Выходные данные

Если хотя бы одна требуемая вселенная существует, выведите на первой строке Possible, затем m строк, i-я из которых содержит два натуральных числа ai и bi (0 < ai, bi ≤ n, все неупорядоченные пары {ai, bi} различны), разделенных ровно одним пробелом – номера планет, между которыми есть путь перемещения.

Иначе выведите Impossible.

Примеры

Входные данные
3 3
Выходные данные
Possible
1 3
1 2
2 3
Входные данные
2 0
Выходные данные
Impossible