G - 貢物（Tribute） 解説 /

実行時間制限: 2.5 sec / メモリ制限: 256 MB

問題文

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|)が与えられる。
  • ここで、A_i,B_iはそれぞれ、「条件」を表しており、A_i,B_i２つの条件を同時に満たしてはならないというのが、村iの掟である。
  • 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)が与えられる。

配点

この問題には部分点が設定されている。

  • データセット1は、M(1≦M≦10^3)を満たし、正解すると15点が得られる。
  • データセット2では追加の制約はなく、正解すると125点が得られる。

    • 出力

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

    入力例1

    3 4
1 2
-2 -3
-1 3
1 -2
1 3
2 5
6 4

    出力例1

    Possible
Possible
Possible

    例えば、村5には何も捧げないことができ、村6には｛貢物1と貢物3｝を捧げることができ、村7には｛貢物2｝を捧げることができる。

    入力例2

    3 4
-1 -2
2 3
1 -2
2 -3
1 4
2 5
6 3

    出力例2

    Possible
Possible
Impossible

    入力例3

    4 20
3 -2
4 -3
3 -1
-2 -3
-1 2
2 -4
2 -3
4 -1
1 4
-1 -3
4 2
1 -3
-2 -1
2 3
3 -4
-4 -2
-4 1
-1 -4
2 1
-4 -3
1 11
16 2
6 20
8 12
22 15
18 5
23 7
9 10
13 26
19 21
4 3
28 31
14 24
27 30
29 25
17 34
36 32
35 33
37 38

    出力例3

    Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Impossible
Possible
Impossible