[USACO10DEC] The Trough Game S

Farmer John and Bessie are playing games again. This one has to do with troughs of water. Farmer John has hidden N (1 <= N <= 20) troughs behind the barn, and has filled some of them with food. Bessie has asked M (1 <= M <= 100) questions of the form, 'How many troughs from this list (which she recites) are filled?'. Bessie needs your help to deduce which troughs are actually filled. Consider an example with four troughs where Bessie has asked these questions (and received the indicated answers): 1) 'How many of these troughs are filled: trough 1' --> 1 trough is filled 2) 'How many of these troughs are filled: troughs 2 and 3' --> 1 trough is filled 3) 'How many of these troughs are filled: troughs 1 and 4' --> 1 trough is filled 4) 'How many of these troughs are filled: troughs 3 and 4' --> 1 trough is filled From question 1, we know trough 1 is filled. From question 3, we then know trough 4 is empty. From question 4, we then know that trough 3 is filled. From question 2, we then know that trough 2 is empty. 农夫约翰和贝西又在玩游戏。这个游戏需要很多个槽。 农夫约翰在谷仓里藏起来了N（1<=N<=20）个槽，并且他已经把其中的一些装上了食物。贝西以“在这个表里（表由贝西提供）有多少个槽里有食物？”的形式问了M（1<=M<=100）个问题。 现在，贝西想知道，哪几个槽里有食物？ 这里有一个样例： （1）在第一个槽里有多少个槽里有食物？——1个 （2）在第二个和第三个槽里有多少个槽里有食物？——1个 （3）在第一个和第四个槽里有多少个槽里有食物？——1个 （4）在第三个和第四个槽里有多少个槽里有食物？——1个 从第一个问题可以知道，第一个槽是有食物的。 从第二个问题可以知道，第四个槽是没有食物的。 从第三个问题可以知道，第三个槽是有食物的。 从第四个问题可以知道，第二个槽是没有食物的。

\* Line 1: Two space-separated integers: N and M \* Lines 2..M+1: A subset of troughs, specified as a sequence of contiguous N 0's and 1's, followed by a single integer that is the number of troughs in the specified subset that are filled.

\* Line 1: A single line with: \* The string 'IMPOSSIBLE' if there is no possible set of filled troughs compatible with Farmer John's answers. \* The string 'NOT UNIQUE' if Bessie cannot determine from the given data exactly what troughs are filled. \* Otherwise, a sequence of contiguous N 0's and 1's specifying which troughs are filled.

4 4 
1000 1 
0110 1 
1001 1 
0011 1 

1010