二分图

【题目描述】

给定一个两侧各有$n$和$m$个点的二分图（保证$n≤m$），对于每条边，你需要判断原图是否存在一个大小为$n$，且包含了这条边的匹配。

【输入】

第一行两个整数$n，m$。 接下来$n$行，每行一个长度为$m$的字符串，对于第$i + 1$行的第$j$个字符，如果它是$1$，则左侧的点$i$与右侧的点$j$之间存在连边，否则不存在。

【输出】

输出$n$行，每行一个长度为$m$的字符串，对于左侧的点$i$与右侧的点$j$，如果不存在一组大小为$n$的匹配包含它们之间的连边，或它们之间没有连边，则第i行的第$j$个字符应为 $1$，否则为$0$。

【输入样例】

4 4
1111
1000
1111
1111

【输出样例】

1000
0111
1000
1000

【提示】

【样例输入2】

4 5
10000
10000
10000
10000

【样例输出2】

11111
11111
11111
11111

【样例输入3】

4 4
1111
1110
1100
1000

【样例输出3】

1110
1101
1011
0111

【数据规模】 对于50%的数据，$1≤n≤15，1≤m≤30$； 对于100%的数据，$1≤n≤300，1≤m≤1500$。

4 5\n10000\n10000\n10000\n10000

11111\n11111\n11111\n11111

4 4\n1111\n1110\n1100\n1000

1110\n1101\n1011\n0111