题目描述

战斗一败再败，让 Arthur 不得不休整自己的部队。一次偶然的事件让 Arthur 醒悟到了失败的原因（无从查之），于是，Arthur 开始调查自己内部的问题。经过一段时间的调查，Arthur 找出了 $N$ 个最有可能是内奸的人。之后对这些人分别进行了询问调查，现在想叫你帮忙判断一下谁是内奸。内奸只会说假话，而不是内奸的一定会说真话。由于内奸可能有多个，所以 Arthur 想你找出所有的可能。

输入格式

第一行 $N,M$ 为被调查的人数和询问到的事件个数（$1\le N\le 25$，$1\le M\le 600$）。之后 $M$ 行，每行三个数 $A,B,P$，表示 $A$ 对 $B$ 的评价，$P=1$ 表示 $A$ 说 $B$ 是内奸，$P=0$ 表示 $A$ 说 $B$ 不是内奸。

输出格式

输出所有的可能。对于每个可能先输出编号 “case i: ”（注意空格），接着如果有内奸就输出一个升序的序列，为内奸的编号；没有内奸就输出“None”。

对于情况之间的顺序，按第一个数的大小升序排列，第一个数一样则按第二个数，以此类推；

若出现“1 2 3”和“1 2 3 4”两种可能都成立的情况，先输出“1 2 3 4”，再输出“1 2 3”；

“None” 永远在最后输出。

如果没有任何解则输出 “No solution”。

3 3
1 2 1
1 3 1
2 1 1

case 1: 1
case 2: 2 3

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

No solution

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

case 1: 1 2 3
case 2: None

数据规模

对于 $100\%$ 的数据，$1\le N\le 25, 1\le M\le 600$。