====== دروغگو ======


$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$‌را بنویسید.


===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|10 \\ 5 \\ 1 2 even \\ 3 4 odd \\ 5 6 even \\ 1 6 even \\ 7 10 odd | 4|
|10 \\ 5 \\ 1 2 even \\ 1 4 odd \\ 2 4 even \\ 1 10  even \\ 3 10 even | 6|
</WRAP>

  * [[سوال ۴|سوال بعد]]
  * [[سوال ۲|سوال قبل]]