Информанты
Агентство контрразведки Макондо (АКМ) намерено оценить качество своих информаторов с помощью простого, но эффективного метода, который определяет надежность группы информаторов.
АКМ оценивает доверие к группе информаторов, проводя опрос: каждый информатор высказывает свое мнение о других, включая себя. В результате опроса АКМ получает утверждения вида "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 (этот случай следует игнорировать).
Выходные данные
Для каждого тестового случая выведите в отдельной строке максимальное количество надежных информаторов согласно ответам в опросе.