UOJ Logo Universal Online Judge

UOJ

#210. 【UER #6】寻找罪犯

附件下载 统计

通过一些不可描述的方式,妹滋滋算出了 51% 的得票率,于是就她就把这个公开给了广大用户 —— UOJ 解散已成定局。

几个小时后,UOJ 创始人伏特跳蚤国王宣布辞职,即日起退出 UOJ 团队。

这两个消息在算法竞赛界引起了轩然大波,“UOJ 是什么”“废除UOJ有什么影响” 马上成为了网民们的搜索热点并出现在了各大搜索网站的首页上。

著名的大水群和三连击发源地 —— Universal OJ 用户群随之解散,导致大量 OI 水狗们无处可水。一段时间后,圈子里渐渐传出了恢复 UOJ 的呼声,更有一些人将这个烂摊子归咎于那些投票通过的用户 —— 他们决定找出这些人并加以指责。

经过一段时间的搜索,他们找到了 n 个嫌疑人,编号为 1n,导致 UOJ 解散的犯人就在他们之间。严刑拷打之下,他们交代了一些供词,供词有两类:

  1. xiyi 是犯人。
  2. xiyi 不是犯人。

然而,让事情变得复杂的是,犯人们并不打算背锅,所以他们的供词不总是真的,同时,为了不闹乌龙暴露自己,每一个犯人的所有供词最多有一句是假的,而不是犯人的嫌疑人的供词总是真的。

现在给出了全部的 m 条供词,你需要找出哪些人是犯人。如果有多解,输出任何一组解即可。

输入格式

第一行两个正整数 n,m,表示犯人数目与供词数目。

接下来 m 行,每行三个整数 xi,yi,ti。其中 ti=0 表示 xiyi 是犯人,ti=1 表示 xiyi 不是犯人。

输出格式

第一行一个整数 c 表示犯人的数目。

第二行 c 个整数 pi,按照升序输出所有犯人的编号。

如果不存在一个犯人的集合使得供词满足条件,输出一行一个单词 "Impossible"。

样例一

input

2 2
1 2 0
2 1 0

output

2
1 2

explanation

容易看出除了没有犯人的情况,其他三种情况都是满足条件的。

样例二

input

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

output

Impossible

explanation

不论如何,第 3,4 条证言都一定是真的,而这两条证言互相矛盾。

样例三

见样例数据下载。

限制与约定

由于一些原因,本题使用捆绑测试。每个子任务有若干个测试点,分为 5 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

子任务 分值 n的规模 m的规模 其他限制
1101010
2155×104105每个嫌疑人最多说 2 条供词
315104105每个嫌疑人最多说 10 条供词
420300105m=n(n1) 且对于所有 1p,qnpqp,qxi=p,yi=q 恰好出现一次
540105105

对于所有数据,1n,m1051xi,yinti{0,1}

时间限制:2s

空间限制:512MB

下载

样例数据下载