Ідеальні вибори
У певній країні (не можу пригадати якій), кандидати {1, 2, ..., N} змагаються на парламентських виборах. Опитування ставить запитання: "Який результат виборів між двома кандидатами на ваш вибір зробить вас щасливим?". Отримані відповіді представлені в таблиці нижче, де кандидати i та j не обов'язково різні, тобто може бути, що i = j. Є M відповідей опитування, деякі з яких можуть повторюватися або бути ідентичними. Завдання полягає в тому, щоб визначити, чи може існувати результат виборів, який задовольняє всі M відповіді. Ми називаємо такий результат виборів досконалим. Відповідь на задачу дорівнює 1, якщо досконалий результат виборів існує, і 0 в іншому випадку.
Напишіть програму, яка зчитує набори даних з вхідного текстового файлу.
Вхідні дані
Кожен набір даних відповідає одному випадку задачі і починається з двох цілих чисел: 1 ≤ N ≤ 1000 та 1 ≤ M ≤ 1000000. Набір даних продовжується M парами ±i ±j зі знакових чисел, 1 ≤ i, j ≤ N. Кожна пара кодує відповідь опитування наступним чином:
Вхідні дані розділені пробілами, завершуються кінцем файлу і є коректними.
Вихідні дані
Для кожного набору даних програма виводить результат закодованої задачі виборів. Результат, 1 або 0, виводиться на стандартний вихід з початку рядка. Не повинно бути порожніх рядків у виході. Нижче наведено приклад вхідних/вихідних даних.