問題文


あなたはある画像をコピーしたいです。画像は縦マス、横マスの格子状の各マスに色が塗られたものです。色は全部で色あり、上から行目、 左から列目のマスの色はであらわされます(ただし、以上以下の数字で、一つの数字と一つの色が一対一対応します)。 残念ながら、あなたの使うコピー機は「白黒印刷」しかできません。

下記に挙げる条件を満たすような情報を保持しながら、「白黒印刷」、すなわち、画像を色のみで表現すること、 が出来るなら”possible”を、出来ないなら”impossible”を出力してください。

■条件

1.入力画像で同じ色であるマスは、出力画像においても同じ色で塗られている。

2.入力画像において色の境目である辺は、出力画像においても色の境目である。

制約


  • を満たす任意のに対して、を満たす組が存在する

入力


入力はすべて整数である。

...

...

...

...

出力


題意の「白黒印刷」が可能ならpossibleを、不可能ならimpossibleを出力してください。

サンプル


入力1
2 2 4
1 2
3 4
出力2
possible

例えば、3→2、4→1と塗り替えれば、条件を満たす2色の画像となります。

ここで、頂点で接している2と3などは、同じ色になっても構わないことに注意してください。

入力2
2 2 3
1 1
2 3
出力2
impossible

Submit


Go (1.14)