{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eМанао решил устроить вечеринку. Он ярко украсил свою хату, тщательно подобрал меню, созвал узкий круг друзей... и вдруг осознал, что забыл про подарки!\u003c/p\u003e\n\n\u003cp\u003eНа своих вечеринках Манао всегда дарит гостям подарки. Более того, он всегда дарит каждому что-нибудь такое, чему тот будет рад. Сами гости тоже приносят подарки, каждый по одной штуке. Так как времени осталось немного, Манао не успеет накупить подарков, поэтому ему нужно найти способ выкрутиться из ситуации. И тогда его осеняет гениальная идея: перераспределить принесённые гостями подарки между ними! Естественно, отдать человеку принесённый им же подарок нельзя. Манао хорошо знает своих друзей и заранее может сказать, кому из них понравится принесённый кем подарок.\u003c/p\u003e\n\n\u003cp\u003eНо, к сожалению, может так случиться, что распределить подарки так, чтобы все друзья были рады, не получится. Поэтому Манао решился позвать вдобавок ещё некоторое количество знакомых. Манао хорошо знает и их, и поэтому может с уверенностью предсказать, кто что принесёт и чему будет рад. Обижать знакомых Манао тоже не хочет, поэтому каждый из них также должен получить подарок, которому будет рад. Но чтобы не превращать вечеринку в полный балаган, Манао пригласит наименьшее количество знакомых, которое обеспечит, что распределить подарки между всеми гостями так, чтобы каждый был рад, получится.\u003c/p\u003e\n\n\u003cp\u003eУ Манао \u003cstrong\u003eN\u003c/strong\u003e друзей и \u003cstrong\u003eM\u003c/strong\u003e других знакомых. Пронумеруем друзей числами от \u003cstrong\u003e1\u003c/strong\u003e до \u003cstrong\u003eN\u003c/strong\u003e, а знакомых числами от \u003cstrong\u003eN+1\u003c/strong\u003e до \u003cstrong\u003eN+M\u003c/strong\u003e. Вам дана матрица, по которой можно определить, чей подарок кому понравится. Определите наименьшее количество знакомых, которых надо дополнительно позвать. Если это невозможно, выведите число \u003cstrong\u003e-1\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eПервая строка входного файла содержит два числа \u003cstrong\u003eN\u003c/strong\u003e и \u003cstrong\u003eM\u003c/strong\u003e. Каждая из следующих \u003cstrong\u003eN+M\u003c/strong\u003e строк содержит по \u003cstrong\u003eN+M\u003c/strong\u003e символов \"\u003cstrong\u003eY\u003c/strong\u003e\" или \"\u003cstrong\u003eN\u003c/strong\u003e\". \u003cstrong\u003ej\u003c/strong\u003e-ый символ в \u003cstrong\u003ei\u003c/strong\u003e-ой из этих строк обозначает, понравится ли человеку с номером \u003cstrong\u003ei\u003c/strong\u003e подарок человека с номером \u003cstrong\u003ej\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003e2\u003c/strong\u003e ≤ \u003cstrong\u003eN\u003c/strong\u003e ≤ \u003cstrong\u003e100\u003c/strong\u003e, \u003cstrong\u003e0\u003c/strong\u003e ≤ \u003cstrong\u003eM\u003c/strong\u003e ≤ \u003cstrong\u003e100\u003c/strong\u003e. Ни одному гостю не может понравиться свой же подарок.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eВыведите \u003cstrong\u003e-1\u003c/strong\u003e, если никакое множество знакомых не спасёт вечеринку Манао, и размер такого минимального множества в противном случае.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eNote\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eВ первом примере можно пригласить человека с номером 3, а потом отдать гостю 2 подарок, принесённый гостем 3, гостю 3 подарок, принесённый гостем 1, а гостю 1 подарок гостя 2. В третьем примере можно, пригласив обоих знакомых, обменять подарки первого и второго друзей, четвертому отдать подарок третьего, третьему --- пятого, а пятому --- четвертого.\u003c/p\u003e\n\n"}},{"title":"Example","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\u003e2 2\nNYYY\nNNYN\nYNNN\nNYNN\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}