$n$ نفر $x_2،x_1$،… و $x_n$ به عنوان متهم قتل‌های زنجیره‌ای در کشور اوشانگولولو دستگیر شده‌اند. از آقای $A$‌ به عنوان متهم اصل پرونده سوالاتی به این صورت پرسیده شده است که آیا او از افراد $x_i$ تا $x_j$ تعداد فردی را می‌شناسد یا تعداد زوجی را. پاسخ او یکی از جواب‌های $odd$ یا $even$ بوده است. با توجه به این‌که اصولا متهمین آدم‌های راستگویی نیستند، این امکان وجود دارد که شخص $A$‌جواب دروغ هم بگوید. در مجموع $m$‌ سوال از شخص $A$ پرسیده‌ایم. فرض کنید $m$ و $n$ از ۱۵۰ بیش‌تر نیستند.

در سطر اول پرونده‌ی ورودی، عدد $n$، در سطر بعدی عدد $m$ و در $m$‌ سطر بعدی در هر سطر دو عدد $i$ و $j$ و یک پیغام $odd$ یا $even$‌ آمده است.

می‌خواهیم کوچک‌ترین عدد $i$ را پیدا کنیم به طوری که پس از شنیدن جواب $i$ سوال اول، بتوانیم نتیجه بگیریم که $A$ حتما در یکی از این سوال‌ها دروغ گفته است. در صورت عدم وجود چنین عددی، $i$ را برابر $m+1$ بگیرید. در پرونده‌ی خروجی عدد $i$‌را بنویسید.

• سوال بعد
• سوال قبل