AT_tkppc2016_g 貢物（Tribute）

[problemUrl]: https://atcoder.jp/contests/tkppc2/tasks/tkppc2016_g joisinoお姉ちゃんの次の仕事は、ゲームのテストプレイである。 このゲームでは、主人公は情報を得るために、様々な村を訪れる。 村人から情報を得るには、適切に貢ぎ物をいくつか選び、村に捧げなくてはならない（ここで、$ 0 $個の貢物を捧げても、すなわち何も捧げなくてもよい）。 貢ぎ物の種類は$ N $種類あり、$ 1～N $の番号がつけられている。 また、村は$ M $個あり、$ 1～M $の番号がつけられている。 そして、それぞれの村には、貢ぎ物に関する掟がある。 二つ以上の村が、同じ掟を持つことはない。 この掟は、ある二つの「条件」を同時に満たしてはならないと言うものである。 「条件」とは、「ある貢ぎ物$ X $を捧げる」、もしくは、「ある貢ぎ物$ X $を捧げない」、というものである。 さらに、ストーリーが進行するに連れ、村の合併が行われる。 $ i $回目の合併では、村$ P_i $と村$ Q_i $が合併し、村$ M+i $になる。 合併の際には必ず、村$ P_i $と村$ Q_i $が存在することが保証され、また合併のあとは、村$ P_i $と村$ Q_i $は消滅する。 この時、新しくできた村には、合併元の村の掟がすべて残る。 村の合併は、存在する村が村$ 2M-1 $の一つになるまで行われる。 村$ 1 $〜村$ M $には、掟をすべて守る貢物の組み合わせが存在するが、村$ M+1 $〜村$ 2M-1 $では、掟が互いに矛盾し、掟をすべて守るような貢物の組み合わせが存在しないかもしれない。 joisinoお姉ちゃんの仕事は、村$ M+1 $〜村$ 2M-1 $について、掟をすべて守るような貢物の組み合わせがあるかどうかを判定するプログラムを作ることである。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_M $ $ B_M $ $ P_1 $ $ Q_1 $ $ P_2 $ $ Q_2 $ : $ P_{M-1} $ $ Q_{M-1} $ - $ 1 $行目には、貢物の種類の数を表す整数$ N(1\ ≦\ N\ ≦\ 10^5) $と、村の数を表す整数$ M(2\ ≦\ M\ ≦\ 10^5) $が与えられる。 - 続く$ M $行のうち$ i $行目には、$ i $番目の村の掟を表す整数。$ A_i(1≦|A_i|≦N),B_i(1≦|B_i|≦N)(|A_i|≠|B_i|) $が与えられる。 > 1. ここで、$ A_i,B_i $はそれぞれ、「条件」を表しており、$ A_i,B_i $２つの条件を同時に満たしてはならないというのが、村$ i $の掟である。 > 2. $ A_i $が正のときは、貢物$ |A_i| $を捧げるという条件を表しており、$ A_i $が負のときは、貢物$ |A_i| $を捧げないという条件を表している。$ B_i $についても同様である。 - 続く$ M-1 $行のうち$ i $行目には、合併する村を示す整数$ P_i(1≦P_i＜M+i),Q_i(1≦Q_i＜M+i) $が与えられる。

出力は$ M-1 $行からなる。 $ i $行目には、村$ M+i $について、掟をすべて守るような貢物の組み合わせがある場合は$ "Possible" $、ない場合は$ "Impossible" $と出力せよ。

### 配点 この問題には部分点が設定されている。 3. データセット$ 1 $は、$ M(1≦M≦10^3) $を満たし、正解すると$ 15 $点が得られる。 4. データセット$ 2 $では追加の制約はなく、正解すると$ 125 $点が得られる。 ### Sample Explanation 1 例えば、村$ 5 $には何も捧げないことができ、村$ 6 $には｛貢物$ 1 $と貢物$ 3 $｝を捧げることができ、村$ 7 $には｛貢物$ 2 $｝を捧げることができる。