2443. [HZOI 2016]MC之旅：逃离基友

【题目描述】

自从miner在上次被好友们陷害后，顿时感到前途一片黑暗，于是miner逃离了基友们，独自来到了地下挖矿。但是基友们突然发现miner不见后，全体出动要把miner抓捕回来。于是miner只得一边提防着基友们一边挖矿，还需要无时无刻地小心基友们布下的陷阱。基友们购买了领域中的各种陷阱，在miner周围布下了层层陷阱；但是都被miner一一躲过。于是，基友们下了狠心，在miner挖矿的矿洞里布下了两排钻石矿，但是，这两排钻石矿又连接着非常复杂的机关。而在miner挖矿的时候，他发现这两排钻石矿，深知天上不会掉馅饼的miner马上就推断出这是基友们的陷阱，但是miner还是不想放弃这么多钻石也不想被基友发现，于是miner决定了，每一列的两个钻石矿中，miner需要且只能挖走一个。但是，这个机关远没有那么简单，miner死了一半多的脑细胞，终于验算出了所有不惊动基友们时需要满足的条件。也就是说，只有当满足所有的这些条件时，miner才可以成功得到钻石，否则，He will die…..

这些条件分别有：

1.

i       //表示编号为i的钻石矿一定需要挖去

2.

not i   //表示编号为i的钻石矿一定不可以被挖去

3.

i and j

4.

i and (not j)

5.

i or j

6.

i or (not j)

7.

not (i and j)

8.

not (i or j)

9.

i xor j //表示异或,即当i=true,j=false或i=false,j=true是表达式为true

10.not (i xor j)

11.i xor (not j)

12.(not i) or (not j)

【输入格式】

多组测试数据

   每组测试数据第一行包括两个正整数n，m表示有n对钻石矿，m组限制

   接下来有m行，每行描述一种限制。

【输出格式】

只有当miner列出的所有表达式的值均为真的时候，才算miner成功；

（注意：假如说我们挖去了i这个矿，那么我们称i=true）

如果miner可以成功，则按字典序输出字典序最小的方案；

否则输出”die”（不包括双引号）

【样例输入】

4 6



3 1 4



5 5 6



5 5 7



2 3



9 1 2



9



5 4

【样例输出】

1 4 6 7

【提示】

所以，满足条件的选择就是

1 4 6 7

数据范围

对于20% 正整数 n <= 1,m <=2;

对于100% 正整数 n,m<= 10000;

【来源】

lyc