Problem Description

joisino's next job is to test play a game.
In this game, the protagonist visits various villages to obtain information.
To get information from villagers, they must choose some appropriate tributes and offer them to the village (here, offering 0 tributes, i.e., offering nothing, is also allowed).
There are $ N $ types of tributes, numbered from $ 1 $ to $ N $.
There are also $ M $ villages, numbered from $ 1 $ to $ M $.
Each village has rules regarding tributes.
No two villages have the same rules.
These rules state that two specific "conditions" must not be met simultaneously.
A "condition" is either "offer a certain tribute $ X $" or "do not offer a certain tribute $ X $".
As the story progresses, villages merge.
In the $ i $-th merge, village $ P_i $ and village $ Q_i $ merge to form village $ M+i $.
It is guaranteed that village $ P_i $ and village $ Q_i $ exist before the merge, and after the merge, village $ P_i $ and village $ Q_i $ disappear.
The new village retains all the rules of the merging villages.
Village mergers continue until there is only one village, numbered $ 2M-1 $.
For villages $ 1 $ to $ M $, there exists a combination of tributes that satisfies all the rules. However, for villages $ M+1 $ to $ 2M-1 $, the rules might conflict, and there might not be a combination of tributes that satisfies all the rules.
joisino's job is to write a program that determines whether there is a combination of tributes that satisfies all the rules for villages $ M+1 $ to $ 2M-1 $.

Input Format

The input is given from the standard input in the following format:

$ 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} $

• The first line contains the number of tribute types $N(1\ ≦\ N\ ≦\ 10^5)$ and the number of villages $M(2\ ≦\ M\ ≦\ 10^5)$.

• The next $ M $ lines contain the rules for each village. The $ i $-th line contains integers $ A_i(1≦|A_i|≦N),B_i(1≦|B_i|≦N)(|A_i|≠|B_i|) $, representing the rules for village $ i $.

  1. Here, $ A_i,B_i $ represent the "conditions". The rule for village $ i $ is that both conditions $ A_i $ and $ B_i $ must not be met simultaneously.
  2. If $ A_i $ is positive, it represents the condition "offer tribute $ |A_i| $". If $ A_i $ is negative, it represents the condition "do not offer tribute $ |A_i| $". The same applies to $ B_i $.

• The next $ M-1 $ lines contain the villages to be merged. The $ i $-th line contains integers $ P_i(1≦P_i＜M+i),Q_i(1≦Q_i＜M+i) $, indicating the villages to be merged.

Output Format

The output consists of $ M-1 $ lines.
The $ i $-th line should output $ "Possible" $ if there is a combination of tributes that satisfies all the rules for village $ M+i $, and $ "Impossible" $ otherwise.

Sample Input and Output

Sample Input #1

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

Sample Output #1

Possible
Possible
Possible

Sample Input #2

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

Sample Output #2

Possible
Possible
Impossible

Sample Input #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

Sample Output #3

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

Notes/Hints

Scoring

This problem has partial scoring.

1. Dataset $ 1 $ satisfies $ M(1≦M≦10^3) $ and awards $ 15 $ points for a correct answer.
2. Dataset $ 2 $ has no additional constraints and awards $ 125 $ points for a correct answer.

Sample Explanation 1

For example, village $ 5 $ can offer nothing, village $ 6 $ can offer tributes $ 1 $ and $ 3 $, and village $ 7 $ can offer tribute $ 2 $.

见题面 Input 部分

见题面 Output 部分