{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch3 class\u003d\"problem_subtitle\"\u003eBackground\u003c/h3\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOnce every generation, there is a tournament known as Mortal Kombat, which was designed by the Elder Gods for\u0026nbsp;the main purpose to save Earthrealm from the dark forces of Outworld. If the forces of Outworld win the\u0026nbsp;tournament ten consecutive times, the Emperor will be able to invade and conquer Earthrealm. Thus far, Outworld\u0026nbsp;has won nine straight victories, making the upcoming tournament the tenth, and possibly final one, for\u0026nbsp;the\u0026nbsp;Earthrealm.\r\n\u003cbr\u003e\r\n\u003cbr\u003e\u003ci\u003eFrom Wikipedia, the free encyclopedia\u003c/i\u003e\u003c/div\u003e\u003c/div\u003e\u003ch3 class\u003d\"problem_subtitle\"\u003eProblem\u003c/h3\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThere are \u003ci\u003eN\u003c/i\u003e monsters and \u003ci\u003eM\u003c/i\u003e 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.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe 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.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eFor 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\r\nlead to the conquest of the Earth, because later Shang Tsung will defeat his opponent.\r\nThis means that the pair Liu Kang vs. Goro should not be selected for the first fight.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eFind out which pairs cannot be chosen by Raiden if he wants to save the freedom of humanity.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains integers \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eM\u003c/i\u003e (\u003cnobr\u003e1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 300;\u003c/nobr\u003e \u003cnobr\u003e\u003ci\u003eN\u003c/i\u003e ≤ \u003ci\u003eM\u003c/i\u003e ≤ 1500\u003c/nobr\u003e). Next lines contain the binary matrix \u003ci\u003eA\u003c/i\u003e with \u003ci\u003eN\u003c/i\u003e rows and \u003ci\u003eM\u003c/i\u003e columns. \u003ci\u003eA\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e\u0026nbsp;\u003d\u0026nbsp;1 if and only if \u003ci\u003ej\u003c/i\u003e-th Earth warrior can defeat \u003ci\u003ei\u003c/i\u003e-th monster.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput matrix \u003ci\u003eB\u003c/i\u003e with \u003ci\u003eN\u003c/i\u003e rows and \u003ci\u003eM\u003c/i\u003e columns. \u003ci\u003eB\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e should be equal to one if the first battle cannot be held between \u003ci\u003ei\u003c/i\u003e-th monster and \u003cnobr\u003e\u003ci\u003ej\u003c/i\u003e-th\u003c/nobr\u003e human, and zero otherwise.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4\r\n1111\r\n1000\r\n1111\r\n1111\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1000\r\n0111\r\n1000\r\n1000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 5\r\n10000\r\n10000\r\n10000\r\n10000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11111\r\n11111\r\n11111\r\n11111\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}