bzoj#P1165. [Baltic2008]Gates
[Baltic2008]Gates
题目描述
厌倦了你的工作,你从 IT 行业跳槽到了一家水产养殖公司。 你的第一项任务是把两个水槽分隔开。尝试了操作手册的内容并仔细观察之后,你了解了水槽的工作机制。 两个水槽由 条通道相连,每个通道上有两个水闸。只有两个水闸都打开时通道才开启,其余情况下通道都是封闭的。 这 个水闸的状态由开关控制。每个水闸的状态恰好由一个开关控制,当然某个开关可能控制多个水闸或者不控制任何水闸。一条通道上的两个水闸也有可能由同一个开关控制。 开关一共有 个,编号为 ,每个开关有两种状态:开和关。而水闸受开关控制的方式有两种:
- 开关开时水闸打开,开关关时水闸关闭。
- 开关关时水闸打开,开关开时水闸关闭。
输入格式
输入的第一行包含两个整数 和 。 接下来 行每行包含了一条通道的信息,由四个整数 表示。 和 表示控制两个水闸的开关编号,而 和 为 或 ,表示水闸受开关控制的方式。 表示开关 关时水闸关,以此类推。
输出格式
如果存在一种开关的状态使得所有通道都封闭,则输出 行,每行一个整数 或 。第 行为 表示编号为 的开关应当关,为 则表示开关应当开。
如果不存在这样的状态,输出一行 IMPOSSIBLE
。
3 2
1 0 2 1
1 0 2 0
1 1 2 1
0
1
数据规模与约定
对所有数据,。
需要 SPJ。