← 返回题目列表

Codeforces · 228/E

E. 通往贝尔兰的道路是用善意铺成的

中文机器翻译题面 查看原题

Berland有n个城市,其中一些城市通过双向道路连接。对于每条道路,我们都知道它是否铺有沥青。

贝尔兰国王瓦莱拉二世想要为贝尔兰的所有道路铺上沥青,为此他召集了一群工人。瓦莱拉每天都会选择一个城市,并命令工作人员为来自该城市的所有道路铺上沥青。英勇的船员们一天之内就完成了国王的命令,然后工人们就回家了。

不幸的是,并不是一切都像瓦莱拉二世所希望的那样美好。这群人的主要部分是加斯塔贝特人(gastarbeiters)——一群热心但不擅长理解贝尔兰语命令的非法移民。因此,在接到为来自城市部分地区的道路铺设沥青的命令后,该小组为来自该城市的所有非沥青道路铺设了沥青,反之亦然,从有沥青的道路上铺设了沥青。

得知这一进展后,瓦莱拉二世非常沮丧,但由于已经来不及改变任何事情,他要求你制定一个程序,确定是否可以在最多 n 天内以某种方式为伯兰迪亚道路铺沥青。帮助国王。

输入

第一行包含两个空格分隔的整数 n, m $$( 1 \leq n \leq 100 ; \; 1 \leq m \leq \frac { n \cdot ( n - 1 ) } { 2 } )$$ — 相应的 Berland 城市和道路的数量。接下来的 m 行包含 Berland 的道路描述:第 i 行包含三个空格分隔的整数 ai、bi、ci (1 ≤ ai, bi ≤ n; ai ≠ bi; 0 ≤ ci ≤ 1)。前两个整数 (ai, bi) 是第 i 条道路连接的城市的索引,如果道路最初铺有沥青,则第三个整数 (ci) 等于 1,否则等于 0。

考虑 Berland 的城市索引从 1 到 n,道路索引从 1 到 m。保证两个伯兰迪亚城市之间的道路不超过一条。

输出

在第一行中打印一个整数 x (0 ≤ x ≤ n) — 为所有道路铺设沥青所需的天数。在第二行中打印 x 个空格分隔的整数 — 将工人发送到的城市的索引。按顺序打印城市,其中 Valera 将工人送到柏油路上。如果有多个解决方案,请打印其中任何一个。

如果无法为所有道路铺设沥青,请打印“不可能”(不带引号)。

示例

输入 #1

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

输出 #1

4
3 2 1 3

输入 #2

3 3
1 2 0
2 3 0
3 1 0

输出 #2

Impossible