G - 貢物(Tribute) Editorial

Time Limit: 2.5 sec / Memory Limit: 256 MB

問題文

joisinoお姉ちゃんの次の仕事は、ゲームのテストプレイである。
このゲームでは、主人公は情報を得るために、様々な村を訪れる。
村人から情報を得るには、適切に貢ぎ物をいくつか選び、村に捧げなくてはならない(ここで、00個の貢物を捧げても、すなわち何も捧げなくてもよい)。
貢ぎ物の種類はNN種類あり、1N1~Nの番号がつけられている。
また、村はMM個あり、1M1~Mの番号がつけられている。
そして、それぞれの村には、貢ぎ物に関する掟がある。
二つ以上の村が、同じ掟を持つことはない。
この掟は、ある二つの「条件」を同時に満たしてはならないと言うものである。
「条件」とは、「ある貢ぎ物XXを捧げる」、もしくは、「ある貢ぎ物XXを捧げない」、というものである。
さらに、ストーリーが進行するに連れ、村の合併が行われる。
ii回目の合併では、村PiP_iと村QiQ_iが合併し、村M+iM+iになる。
合併の際には必ず、村PiP_iと村QiQ_iが存在することが保証され、また合併のあとは、村PiP_iと村QiQ_iは消滅する。
この時、新しくできた村には、合併元の村の掟がすべて残る。
村の合併は、存在する村が村2M12M-1の一つになるまで行われる。
11〜村MMには、掟をすべて守る貢物の組み合わせが存在するが、村M+1M+1〜村2M12M-1では、掟が互いに矛盾し、掟をすべて守るような貢物の組み合わせが存在しないかもしれない。
joisinoお姉ちゃんの仕事は、村M+1M+1〜村2M12M-1について、掟をすべて守るような貢物の組み合わせがあるかどうかを判定するプログラムを作ることである。


入力

入力は以下の形式で標準入力から与えられる。

NN MM
A1A_1 B1B_1
A2A_2 B2B_2
:
AMA_M BMB_M
P1P_1 Q1Q_1
P2P_2 Q2Q_2
:
PM1P_{M-1} QM1Q_{M-1}
  • 11行目には、貢物の種類の数を表す整数N(1N105)N(1 ≦ N ≦ 10^5)と、村の数を表す整数M(2M105)M(2 ≦ M ≦ 10^5)が与えられる。
  • 続くMM行のうちii行目には、ii番目の村の掟を表す整数。Ai(1AiN),Bi(1BiN)(AiBi)A_i(1≦|A_i|≦N),B_i(1≦|B_i|≦N)(|A_i|≠|B_i|)が与えられる。
  • ここで、Ai,BiA_i,B_iはそれぞれ、「条件」を表しており、Ai,BiA_i,B_i2つの条件を同時に満たしてはならないというのが、村iiの掟である。
  • AiA_iが正のときは、貢物Ai|A_i|を捧げるという条件を表しており、AiA_iが負のときは、貢物Ai|A_i|を捧げないという条件を表している。BiB_iについても同様である。
  • 続くM1M-1行のうちii行目には、合併する村を示す整数Pi(1PiM+i),Qi(1QiM+i)P_i(1≦P_i<M+i),Q_i(1≦Q_i<M+i)が与えられる。

配点

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

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

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


    入力例1Copy

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

    出力例1Copy

    Copy
    Possible
    Possible
    Possible
    

    例えば、村55には何も捧げないことができ、村66には{貢物11と貢物33}を捧げることができ、村77には{貢物22}を捧げることができる。


    入力例2Copy

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

    出力例2Copy

    Copy
    Possible
    Possible
    Impossible
    

    入力例3Copy

    Copy
    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
    

    出力例3Copy

    Copy
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Possible
    Impossible
    Possible
    Impossible
    


    2025-01-21 (Tue)
    10:27:20 +00:00