8694: BZOJ4694:水题嘉年华

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

水题嘉年华温暖节最盛大的活动,而主办方为了缓解大部分OIer常年把不到妹的问题,特别设置了一个有趣的活动 “脱单连连看”。规则是这样的,有M 个OIer和 M个妹子参加这个节目,主持人在黑板上按照某个顺序写下这N=2M  个人的名字,然后请水题嘉年华的特邀嘉宾Lyra将OIer和妹子配对。具体来说,这M 个名字排成水平的一行,Lyr a要画 M条折线,每条折线不能跨越名字所在的水平线,且必须连接一个OIer和一个妹子,任意两条折线不能相交 。举一个合法例子:   然而,很多OIer其实已经暗地里脱团了,于是每个OIer其实都带来了自己的妹子,只不过想借助这个活动来正大光 明的公布恋情。方便起见我们给每个人一个 0到 M-1的编号,一个OIer和他的妹子编号相同。Lyra的任务就是在合 法条件下连接每个OIer和他的妹子。现在 N个位置中某些位置的人已经确定了,剩下的由Lyra任意填写,Lyra想知 道,是否存在一种填写剩下位置的姓名的方式,使得她能在保证合法的前提下连接每个OIer和他的妹子。填写姓名 要保证0 到 M-1每个编号出现且只出现两次。


输入格式

第一行一个整数 ,以下T 组数据,对于每组数据: 第一行一个整数 表示OIer和妹子的总数目。 第二行 N个整数表示每个位置已经确定的姓名的编号, -1表示这个位置还没有确定。 输入保证 N为偶数且每个编号出现两次或零次。 T<=30,N<=50


输出格式

对于每组数据,若Lyra可以安排剩余的姓名并连接每个OIer和他的妹子 输出”POSSIBLE”,否则输出”IMPOSSIBLE”。(不含引号)


样例输入

2
6
-1 0 -1 -1 0 -1
6
1 -1 2 1 -1 2

样例输出

POSSIBLE
IMPOSSIBLE

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: