Ідеальні вибори#1368
У країні кандидати \{1, 2, \ldots, N\} беруть участь у парламентських виборах. Опитування ставить запитання: "Який результат виборів між будь-якими двома вибраними вами кандидатами зробить вас щасливим?" Дозволені відповіді наведено у таблиці нижче, де кандидати та не обов'язково різні (тобто можливо, що i = j). Є відповідей на опитування, деякі з них можуть повторюватися або бути ідентичними. Завдання полягає у визначенні, чи можливий такий результат виборів, що задовольняє всі відповідей. Такий результат називається ідеальним. Відповідь до задачі — , якщо існує ідеальний результат виборів, і інакше.
Напишіть програму, що зчитує кілька наборів даних з текстового вхідного файлу.
Кожен набір даних відповідає одній задачі та починається з двох цілих чисел: 1 \le N \le 1000 та 1 \le M \le 1000000. Далі йдуть пар \pm i\; \pm j зі знаками, де 1 \le i, j \le N. Кожна така пара кодує відповідь на опитування таким чином:
Вхідні дані розділені пробілами, завершуються кінцем файлу і є коректними.
Для кожного набору даних програма виводить відповідь на закодовану задачу про вибори. Відповідь ( або ) друкується у стандартний вихід на початку нового рядка. Порожніх рядків у виводі бути не повинно. Нижче наведено приклади вхідних та вихідних даних.
Приклад 1