[Usaco2010 Dec]The Trough Game

题目描述

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="" asked="" m="" (1="" questions="" form,="" "how="" many="" from="" this="" list="" (which="" she="" recites)="" are="" filled?".="" needs="" your="" help="" to="" deduce="" which="" actually="" filled.="" consider="" an="" example="" four="" where="" these="" (and="" received="" indicated="" answers):="" 1)="" 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位二进制数X，使得给定的M个数，满足X and Bi=Ci ,Bi ci分别是读入的两个数

---

输入格式

* 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

---

提示

没有写明提示

---

题目来源

Silver