Гра з листом паперу
Обмеження: 2 сек., 256 МіБ
Економічна криза торкнулася багатьох громадян нашої країни. Не оминула вона й мешканця одного з мальовничих сіл Галичини Івана. Тож він, як людина, що не звикла сидіти склавши руки, вирішив, що потрібно вживати якихось заходів з боротьби з кризою. На дозвіллі він часто любив розгадувати головоломки та шаради. Тому не дивно, що йому спало на думку одне на перший погляд дуже прибуткове діло — пропонувати своїм друзям та знайомим зіграти з ним у гру, переможець якої отримає від переможеного невеличку матеріальну «дотацію».
Суть цієї гри полягала в такому. Гравцям дано прямокутний лист паперу, розграфлений на квадрати однакового розміру. Гравці ходять по черзі. Хід полягає в тому, що гравець вибирає один із квадратів, які ще присутні на листі, та вирізає з листа ножицями всі квадрати, які розташовані вище та праворуч від цього квадрату включно з ним. Той, хто зробить останній хід програє. Вам відомо розмір листа та те, що гравці вже зробили декілька ходів.
Необхідно сказати, хто з них виграє при подальшій оптимальній стратегії обох гравців (ходи, що зроблені гравцями до того, не обов’язково відповідають деяким оптимальним стратегіям).
Вхідні дані
У першому рядку дано ціле число \(t\) — кількість тестів.
Далі йде опис кожного тесту. Кожен опис починається рядком з трьома цілими числами \(n\), \(m\) та \(k\). \(n\) — кількість рядків та \(m\) — стовпців, утворених квадратами на листі, \(k\) вказує, скільки ходів вже було зроблено.
У наступних \(k\) рядках йде опис ходів (не обов’язково в тому порядку, у якому їх виконували). Хід описується двома цілими числами \(r\) і \(c\) — номерами рядка і стовпця квадрату відповідно, яким було зроблено хід. Нумерація рядків зверху донизу листа, стовпців — зліва направо. Нумерація починається з нуля.
Усі тести розділені між собою пустим рядком.
Вихідні дані
Для кожного тесту в окремому рядку виведіть FIRST
, якщо
виграє той, хто має робити хід наступним, і SECOND
у
протилежному разі.
Обмеження
\(1 \le t \le 50\),
\(1 \le n, m \le 7\),
\(0 \le k \le 5\),
\(0 \le r_i \le n-1\),
\(0 \le c_i \le m-1\),
\(0 \le k \le n \cdot m-1\),
гарантується, що при попередніх \(k\) ходах не всі квадрати з листа були вирізаними.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
2 3 2 1 0 1 2 3 0 | SECOND FIRST |
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|