Інформанти
Агентство контррозвідки Макондо, скорочено АКМ, прагне перевірити якість своїх інформаторів за допомогою простої, але дуже точної процедури, яка оцінює надійність групи інформаторів.
АКМ визначає довіру до групи інформаторів шляхом проведення опитування довіри серед них: інформатори висловлюють свої конкретні думки про інших, включаючи себе. В результаті опитування АКМ збирає набір тверджень у формі "X каже, що Y надійний" або "X каже, що Y ненадійний". Якщо X виявляється надійним, АКМ вважає, що все, що він або вона каже, можна вважати правдою. В іншому випадку, якщо X ненадійний, його або її думки можуть бути як правдивими, так і хибними. Наприкінці АКМ оцінює ситуацію, визначаючи максимальну кількість інформаторів, які можуть бути надійними згідно з опитаними відповідями.
Наприклад, припустимо, що є чотири інформатори A, B, C і D, з такими опитаними відповідями: "A каже, що B надійний, але D ненадійний", "B каже, що C ненадійний", і "C каже, що A і D надійні". У цьому випадку виявляється, що щонайбільше два інформатори є надійними.
Ваше завдання - допомогти АКМ, написавши ефективну програму, яка, враховуючи результати опитування, обчислює максимальну кількість інформаторів, які можуть бути надійними.
Вхідні дані
Вхідні дані задачі містять кілька випадків. Кожен тестовий випадок починається з рядка з двома невід'ємними цілими числами, i (0 < i ≤ 20) і a (0 ≤ a ≤ 800), розділеними пробілами. i - це кількість інформаторів, а a - кількість відповідей в опитуванні довіри. Потім слідує a рядків, кожен з яких містить два цілі числа x і y (1 ≤ x ≤ i, 1 ≤ |y| ≤ i), розділені пробілами. Якщо y позитивне, рядок означає, що "інформатор x каже, що інформатор y надійний". Якщо y негативне, то рядок означає, що "інформатор x каже, що інформатор y ненадійний". Кінець вводу позначається рядком з двома значеннями 0 (штучний випадок, який слід ігнорувати).
Вихідні дані
Для кожного вхідного випадку виведіть в одному рядку відповідну відповідь, тобто максимальну кількість надійних інформаторів згідно з відповідями в опитуванні.