Once every generation, there is a tournament known as Mortal Kombat, which was designed by the Elder Gods for the main purpose to save Earthrealm from the dark forces of Outworld. If the forces of Outworld win the tournament ten consecutive times, the Emperor will be able to invade and conquer Earthrealm. Thus far, Outworld has won nine straight victories, making the upcoming tournament the tenth, and possibly final one, for the Earthrealm.
From Wikipedia, the free encyclopedia
There are N monsters and M best human fighters participating in the Mortal Kombat. According to the tournament rules, each monster should fight one of the humans (different monsters should fight different humans). If at least one monster wins, the Eathrealm will be conquered by the Emperor of the Outworld. However, the humans can choose the competitors and the order of battles.
The thunder god Raiden, protector of the Earthrealm, should choose the fighters in such a way that all Earth warriors will win their battles. For each monster and each Earth warrior it is known whether the Earth warrior can win the monster. First of all, the fighters for the first battle should be chosen.
For example, suppose that Liu Kang wants to fight Goro, but he is the only warrior able to defeat Shang Tsung, while Goro can be defeated by other warriors, such as Johnny Cage. So, even if Liu Kang will defeat Goro in the first battle, it will inevitably
lead to the conquest of the Earth, because later Shang Tsung will defeat his opponent.
This means that the pair Liu Kang vs. Goro should not be selected for the first fight.
Find out which pairs cannot be chosen by Raiden if he wants to save the freedom of humanity.
The first line contains integers N and M (1 ≤ N ≤ 300; N ≤ M ≤ 1500). Next lines contain the binary matrix A with N rows and M columns. Aij = 1 if and only if j-th Earth warrior can defeat i-th monster.
Output matrix B with N rows and M columns. Bij should be equal to one if the first battle cannot be held between i-th monster and j-th human, and zero otherwise.
Problem Author: Magaz Asanov (prepared by Alexander Ipatov)
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2008