← 返回题目列表

AtCoder · tkppc2016_g

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|)。 表示
  • 在这里,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