BZPRO

#1165. [Baltic2008]Gates

内存限制：162 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

厌倦了你的工作, 你从IT行业跳槽到了一家水产养殖公司.
你的第一项任务是把两个水槽分隔开. 尝试了操作手册的内容并仔细观察之后, 你了解了水槽的工作机制.
两个水槽由n条通道相连, 每个通道上有两个水闸. 只有两个水闸都打开时通道才开启, 其余情况下通道都是封闭的.
这2n个水闸的状态由开关控制. 每个水闸的状态恰好由一个开关控制, 当然某个开关可能控制多个水闸或者不控制任何水闸. 一条通道上的两个水闸也有可能由同一个开关控制.
开关一共有m个, 编号为1; 2;……;m, 每个开关有两种状态: 开和关. 而水闸受开关控制的方式有两种:
l         开关开时水闸打开, 开关关时水闸关闭.
l         开关关时水闸打开, 开关开时水闸关闭.

输入格式

输入的第一行包含两个整数n和m.
接下来n行每行包含了一条通道的信息, 由四个整数a; S a; b; S b表示. a和b表示控制两个水闸的开关编号,而S a和S b为0或1, 表示水闸受开关控制的方式. S i = 0表示开关i关时水闸关, 以此类推.

输出格式

如果存在一种开关的状态使得所有通道都封闭, 则输出m行, 每行一个整数0或1. 第i行为0表示编号为i的开关应当关, 为1则表示开关应当开.
如果不存在这样的状态, 输出一行“IMPOSSIBLE”.

样例

样例输入


			
3 2

1 0 2 1

1 0 2 0

1 1 2 1

样例输出


			
0

1

数据范围与提示

对所有数据, n <= 250000;m <= 500000.

BZPRO Powered by Remmina.
Github Repository