Problem F
Forest Construction

Anton, a young mathematician, comes from the cold region that is northern Sweden. He likes it there, since there are a lot of trees. Lately, however, this has made him a bit sad, since he can’t see the forest because of all the trees. Therefore, he has asked you to construct a forest.

Since Anton is a mathematician, he doesn’t want just any forest – he wants a graph theoretical forest. A forest is a (possibly disconnected) graph without cycles – i.e., a union of disjoint trees.

Anton has already decided how many vertices he wants in his forest, as well as the degree of each vertex. Now, it is your task to construct a forest according to his wishes, or determine that no such forest exists.


The first line of the input is a single integer $0 \le V \le 100$, the number of vertices in his forest.

The next line contains $V$ integers $d_1, d_2, \ldots , d_ V$ ($0 \le d_ i \le 100$ for all $i$). These are the degrees which Anton wants the vertices to have.


The first line of output should be IMPOSSIBLE if it is impossible to construct such a forest.

Otherwise, the first line should be POSSIBLE. The next lines should then contain two integers $1 \le a, b \le V$ each, denoting an edge between vertices $a$ and $b$. Note that the vertex with number $a$ must have exactly degree $d_ a$, i.e. the ordering of the vertices is important.

Sample Input 1 Sample Output 1
1 1 2
1 3
2 3
Sample Input 2 Sample Output 2
1 2
Sample Input 3 Sample Output 3
2 2 2

Please log in to submit a solution to this problem

Log in