401676: GYM100513 A Nasta Rabbara

Sasha just finished watching yet another season of the infamous TV series "Nasta Rabbara", the best show in Berland. The action takes place in a city called Nasta Rabbara that has a population of n people.

In the beginning of the season, all residents of the city were friendly to each other and lived in peace. But as the season developed, people would start getting angry at each other. Specifically, in each of m series, one pair of people quarreled. Note that a pair of people may have quarreled several times throughout the season.

Obviously, Sasha is quite concerned about the situation in Nasta Rabbara. He picked q segments of the season and now wants to analyze them. For convenience, the segments are numbered with integers from 1 to q. The i-th segment contains episodes from the l_i-th to the r_i-th, inclusively. Note that the different segments may overlap, i.e. have common episodes.

When analyzing a given segment, Sasha watches all its episodes and decides which people are good and which are bad (only taking into account the episodes that belong to the segment). Sasha believes that during the segment, good guys should never quarrel with each other, as well as bad guys should never quarrel with each other. I.e. he would accept only a quarrel between a good and a bad guy. Though, sometimes the storyline of a segment can become very complicated, so it's not even possible to classify all characters as either good or bad.

Your task is to help Sasha understand the situation in Nasta Rabbara. For each segment of the season, Sasha needs to determine whether there exists a way to classify all its people as either good or bad, so that:

• no two good guys quarreled over this segment of the season;
• no two bad guys quarreled over this segment of the season.

The first line contains three space-separated integers n, m and q (2 ≤ n ≤ 10⁵; 1 ≤ m, q ≤ 10⁵), denoting the number of people, the number of episodes, and the number of segments Sasha is interested in correspondingly.

The i-th of the next m lines contains a pair of space-separated integers x_i, y_i (1 ≤ x_i < y_i ≤ n), denoting that in the i-th episode person x_i and person y_i quarrel with each other. Assume that all characters of the season are numbered by consecutive integers from 1 to n.

The j-th of the next q lines contains a pair of space-separated integers l_j, r_j (1 ≤ l_j ≤ r_j ≤ m), denoting the boundaries of the j-th segment.

Print q lines. In the j-th line print the word "Possible" if there is a way to classify people as either good or bad considering only the episodes from the l_j-th to the r_j-th inclusive. If there is no such a way, print the word "Impossible". All words should be printed without quotes.

4 3 6
1 2
2 3
1 3
1 1
2 2
3 3
1 2
2 3
1 3

Possible
Possible
Possible
Possible
Possible
Impossible

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

Possible
Possible
Impossible
Possible
Impossible
Impossible

In the first example the answer is "Possible" for all segments, except for the segment that forms a quarrel triangle between people 1, 2 and 3.