n نفر x2،x1،… و xn به عنوان متهم قتلهای زنجیرهای در کشور اوشانگولولو دستگیر شدهاند. از آقای A به عنوان متهم اصل پرونده سوالاتی به این صورت پرسیده شده است که آیا او از افراد xi تا xj تعداد فردی را میشناسد یا تعداد زوجی را. پاسخ او یکی از جوابهای odd یا even بوده است. با توجه به اینکه اصولا متهمین آدمهای راستگویی نیستند، این امکان وجود دارد که شخص Aجواب دروغ هم بگوید. در مجموع m سوال از شخص A پرسیدهایم. فرض کنید m و n از ۱۵۰ بیشتر نیستند.
در سطر اول پروندهی ورودی، عدد n، در سطر بعدی عدد m و در m سطر بعدی در هر سطر دو عدد i و j و یک پیغام odd یا even آمده است.
میخواهیم کوچکترین عدد i را پیدا کنیم به طوری که پس از شنیدن جواب i سوال اول، بتوانیم نتیجه بگیریم که A حتما در یکی از این سوالها دروغ گفته است. در صورت عدم وجود چنین عددی، i را برابر m+1 بگیرید. در پروندهی خروجی عدد iرا بنویسید.