#P2240. ural1676 Mortal Combat
ural1676 Mortal Combat
题目描述
有 只河蟹和 只羊驼。每只河蟹都必须与一只羊驼交战,每只羊驼最多参加一场。已知每一对参赛者交战时羊驼能否获胜。羊驼要安排所有对战,并在每一场对战中获胜。
对每一对河蟹、羊驼,判断是否存在一种安排,使这两只参赛者交战且所有羊驼获胜。如果根本不存在全胜安排,则每一对都不可能选用。
输入格式
第一行两个整数 (,)。
接下来 行,每行 个连续的二进制字符,组成矩阵 。当且仅当第 只羊驼能击败第 只河蟹时,。
输出格式
输出 行,每行 个连续的二进制字符。如果第 只河蟹与第 只羊驼不能出现在任何全胜安排中,输出矩阵的对应位置为 ,否则为 。
样例
4 4
1111
1000
1111
1111
1000
0111
1000
1000
4 5
10000
10000
10000
10000
11111
11111
11111
11111