D. Token o'yini

Ikki o'yinchi grafda o'ynaladigan quyidagi o'yinni o'ynashadi.

Berilgan yo'naltirilmagan oddiy graf \(N\) ta uchga (uchlar \(1\) dan \(N\) gacha raqamlangan) va \(M\) ta qirraga ega. Graf oddiy (ya'ni ikki uch orasida bir nechta qirra bo'lmaydi va uchning o'ziga o'ziga qirrasi yo'q) bo'lib, u albatta bog'langan bo'lishi shart emas — bir nechta alohida qismlardan (komponentalardan) iborat bo'lishi mumkin.

Grafning \(S\) uchida bitta token (belgi) joylashgan.

O'yinchilar navbat bilan yurish qilishadi, birinchi bo'lib \(1-\)o'yinchi yuradi. Har bir yurishda navbatdagi o'yinchi tokenni hozirgi turgan uchdan qirra orqali qo'shni bo'lgan, va o'yin boshidan buyon hali hech qachon token tashrif buyurmagan boshqa uchga ko'chiradi.

Uch bir marta ziyorat qilingandan so'ng u "band" hisoblanadi — token bu uchga ikkinchi marta hech qachon qaytmaydi (garchi qirra mavjud bo'lsa ham).

Navbati kelgan, ammo yura olmaydigan o'yinchi — ya'ni tokenning joriy turgan uchidan chiqadigan barcha qirralar allaqachon band bo'lgan uchlarga olib boradigan (yoki umuman bu uchdan qirra chiqmaydigan) o'yinchi — yutqazadi.

Ikkala o'yinchi ham optimal (eng yaxshi mumkin bo'lgan) strategiyada o'ynaydi, ya'ni har biri o'z g'alabasini ta'minlash imkoniyati bo'lsa, albatta undan foydalanadi.

Sizning vazifangiz — kim g'olib chiqishini aniqlash.

Kiruvchi ma'lumotlar

Birinchi qatorda uchta butun son — \(N\), \(M\) va \(S\) (\(2 \le N \le 1000\), \(0 \le M \le \frac{N(N-1)}{2}\), \(1 \le S \le N\)) beriladi.

Keyingi \(M\) ta qatorning har birida ikkita butun son \(u_i, v_i\) (\(1 \le u_i, v_i \le N\), \(u_i \neq v_i\)) beriladi — bu \(i-\)qirra \(u_i\) va \(v_i\) uchlarini bog'lashini bildiradi. Graf oddiy bo'lgani uchun bir xil qirra takrorlanmaydi.

Chiquvchi ma'lumotlar

Agar ikkala o'yinchi ham optimal o'ynaganda birinchi o'yinchi g'olib chiqsa — first so'zini, aks holda (ikkinchi o'yinchi g'olib chiqsa) second so'zini chop eting (kichik harflarda).

Misollar

1

4 3 1
1 2
2 3
3 4

first

2

4 3 2
1 2
2 3
3 4

first

3

2 0 1

second

Izoh

Birinchi testda token 1-uchda turibdi. 1-o'yinchi tokenni \(1 \rightarrow 2\) ga ko'chiradi, shunda 1-uch band bo'ladi. Keyin 2-o'yinchi \(2 \rightarrow 3\) ga yuradi va 2-uch band bo'ladi. Shundan so'ng 1-o'yinchi \(3 \rightarrow 4\) ga yuradi. Token 4-uchga kelganida, uning yagona qo'shni uchi (3-uch) allaqachon band bo'lgani uchun 2-o'yinchi yura olmaydi va yutqazadi. Natijada birinchi o'yinchi g'alaba qozonadi va first natijasi chiqariladi.