2335. [图论基础与应用]友谊

在现代社会,每个人都有自己的朋友。由于每个人都很忙,他们只通过电话联系。你可以假定A可以和B保持联系,仅当:① A知道B的电话号码;② A知道C的号码,而C能联系上B。如果A知道B的电话号码,则B也知道A的电话号码。 有时,有人可能会碰到比较糟糕的事情,导致他与其他人失去联系。例如,他可能会丢失了电话簿,或者换了电话号码。 在本题中,告知N个人之间的两两联系,这N个人的编号为1~N。给定两个人,如S和T,如果有些人碰到糟糕的事情,S可能会与T失去联系。计算至少多少人碰到糟糕的事情,会导致S与T失去联系。假定S和T不会碰到糟糕的事情。

输入

测试数据的第 1 行为 3 个整数 NST (2≤N≤200,1≤S, T≤N,S≠T)。接下来有 N 行,每行有 N 个整数,如果 i 知道 j 的电话号码,则第 i+1 行、第 j 列上的数字为 1,否则为 0。假定这 N 行中 1 的数目不超过 5000

输出

如果无法使 ST 失去联系,输出“NO ANSWER!”;否则输出的第 1 行为整数 t,表示至少需要 t 个人碰到糟糕的事情,才能导致 ST 失去联系,如果 t 不为 0,则要输出第 2 行,包含 t 个整数,按升序输出这 t 个人的编号,这些整数用空格隔开。 如果存在多个解,则为每个解定义一个分值,输出具有最小分值的解。分值计算方式为:假定解为 A_1, A_2 , … , A_t1≤A1,则分值为 (A1-1)×N t+(A2-1)×N t-1 +…+(At-1)×N。测试数据保证不会出现两个解都具有相同的最小分值。

样例

标准输入 复制文本
3 1 3
1 1 0
1 1 1
0 1 1
标准输出 复制文本
1
2
标准输入 复制文本
9 1 9
1 1 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0
1 1 1 0 1 1 0 0 0
0 1 0 1 0 0 1 0 0
0 1 1 0 1 0 1 1 0
0 0 1 0 0 1 0 1 0
0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 1 1 1
标准输出 复制文本
2
2 3
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 2
通过 1