GRSEQ  Graphic Sequence
Given an integer sequence d = (d_{1}, . . . , d_{n}) determine if there exists a graph G with permutation of d as its sequence of degrees.
Input
The input consists of a sequence of lines. In the first line you are given t<100  the number of sequences to analyze. The description of each of the sequences consists of two lines: in the first line you are given one number n<=100000 (the length of the sequence) and in the second line you are given n nonnegative integers (the sequence elements, all of these numbers are smaller than 100000).
Output
For each of the sequences print in a separate line one of the two words: POSSIBLE if such a graph might exists and IMPOSSIBLE in the opposite case.
Example
Input: 4 3 1 2 2 4 3 2 3 2 5 2 2 4 2 2 4 0 0 0 0 Output: IMPOSSIBLE POSSIBLE POSSIBLE POSSIBLE
Input data sizes
t maxn l 1 10 0.4s 2 100 0.4s 3 1000 0.4s 4 10000 0.4s 5 100000 0.4s t  testcase number maxn  the maximum length of the sequence l  time limit
Hints
Using the Erdős–Gallai Theorem you will be able to implement a linear time algorithm.
You could try also Social Network Existence  very similar problem with smaller inputs.
hide comments
debarun:
20190417 19:13:11
@kuszi I checked for the case you mentioned but still getting wa for 1 and 2. Can you please check? 

kuszi:
20170517 22:14:20
@s1d_3 Please check the case mentioned previously:


s1d_3:
20160305 00:03:08
@kuszi: I tried Havel Hakimi, and Erdos Gallai. I keep getting WA on 1 and 2. Can you check? 

kuszi:
20120901 14:30:42
@Jared Deckard Please consider the case:


Jared Deckard:
20120818 16:39:01
I got WA on test cases 1 & 2, but AC on 3, 4, & 5. Can n=1? 
Added by:  kuszi 
Date:  20120711 
Time limit:  0.400s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Thanks to Robert Janczewski and Adrian Kosowski 