#2365. 「BalticOI 2008」阀门

内存限制:96 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: HeRaNO

题目描述

题目译自 BalticOI 2008 Day1「Gates

成为码农多年的你,已经厌倦了码农生活。你决定跳槽,去做一些不一样的事情。
正在寻找下一份工作的你,被一份水产养殖的工作吸引住了。“太酷了!”并且,鱼是很好的生物 嗯切绘也是这么想的 。所以你毫不犹豫地去应聘了。幸运的是,你成功拿到了 Offer。今天是你工作的第一天。
你的老板已经给你分配了任务:分隔两个蓄水池。你手上的操作指南告诉了你如下信息:
这两个蓄水池之间有一些管道连通,每个管道有两个阀门。当两个阀门同时开启时,这个管道就处于开启状态,反之处于关闭状态。阀门用开关控制。同一个开关会控制一些阀门,但是每一个阀门都只被一个开关控制。有可能一个管道上的两个阀门被同一个开关控制,也可能有开关不控制任何阀门。

gates.png

一个三个管道,两个开关的例子

开关以以下两种方式控制阀门:

  • 当开关闭合时阀门打开,当开关断开时阀门关闭
  • 当开关闭合时阀门关闭,当开关断开时阀门打开

玩了一会儿开关之后你突然意识到你的编程经历会十分有用。给出每个阀门被哪个开关所控制,判断是否可能关闭所有管道,如果可以,找出这种合法配置下每一个开关的状态。

输入格式

标准输入的第一行包含两个整数 n m ,分别表示管道数和开关数。开关被从 1 m 标号。
接下来的 n 行描述管道,一行用四个整数 a,s_a,b,s_b 描述一个管道, a,b 代表控制该管道的开关( 1\le a,b\le m )。 s_a s_b 0 1 ,并与描述中的操作模式相符, s_i=0 表示当且仅当开关 i 断开时阀门关闭, s_i=1 表示当且仅当开关 i 闭合时阀门关闭。

输出格式

如果有可能关闭所有管道,标准输出应包含 m 行,如果开关 i 断开,第 i 行应输出 0 ,如果开关 i 闭合,第 i 行应输出 1 。如果有很多可能的答案,你的程序可以输出任意一种。
如果不可能关闭所有管道,你的程序应输出一行,包含一个单词 IMPOSSIBLE

样例

样例输入 1

3 2
1 0 2 1
1 0 2 0
1 1 2 1

样例输出 1

0
1

样例解释 1

同任务描述中图。

样例输入 2

2 1
1 0 1 0
1 1 1 1

样例输出 2

IMPOSSIBLE

数据范围与提示

对于 30\% 的数据, n\le 40, m\le 20
对于所有数据, 1\le n\le 2.5\times 10^5, 1\le m\le 5\times 10^5