에다마메 에너지 공학

바이오 벤처 ICPC(International Cucumber Planting Company)는 연료용 풋콩을 개발하고 있다. 그들이 벤처 캐피털에 제출한 사업 계획서에 따르면, ICPC 사의 기술로 특별히 품종 개량한 풋콩을 특정 약품으로 화학 처리하면 연료용 에탄올을 얻을 수 있다고 한다(원래는 오이 개량에 매달렸지만 그쪽은 잘 되지 않았다).

그 풋콩이 곧 수확기를 맞는다. 이 풋콩의 꼬투리에는 M개의 콩이 한 줄로 늘어서 있고, 알마다 서로 다른 특성을 지니므로 원래는 각각 다른 화학 처리가 필요하다.

화학 처리에 쓰이는 약품은 모두 N종류다. 각 콩알에는 특성이 2개 있고, 그중 하나만 충족되어도 연료로 만들 수 있다. 특성에는 "어떤 약품을 쓴다"는 것과 "어떤 약품을 쓰지 않는다"는 것의 두 가지가 있다.

• 특성 P(x): 종류 x의 약품이 유효하다(종류 x의 약품을 쓰면 처리할 수 있다)
• 특성 Q(x): 종류 x의 약품에 의해 저해된다, 그 콩알에 유효한 자기분해효소를 지니고 있다(종류 x의 약품을 쓰지 않으면 처리할 수 있다)

예를 들어, 어떤 콩알이 P(x)와 Q(y)의 특성을 지니고 있다면, 이 콩알은 종류 x의 약품을 써서 처리할 수 있고, 종류 x의 약품이 쓰이지 않은 경우에도 종류 y의 약품만 쓰이지 않았다면 처리할 수 있다. 또한 어떤 콩알이 지닌 2개의 특성은 같은 타입일 수도 있는데, 예를 들어 P(x)와 P(y)의 특성을 지니고 있다면 이 콩알은 종류 x 또는 y의 약품을 쓰면 처리할 수 있다.

오랜 연구 개발로 자금이 바닥나려는 ICPC 사에는 풋콩을 한 알씩 꺼내어 각각에 알맞은 처리를 하는 설비에 투자할 여력이 남아 있지 않았다. 대안으로, 0종류 이상의 약품을 혼합해 만든 처리액을 쓰고, 풋콩의 양끝에서 0개 이상의 연속한 콩알을 버린 뒤 가운데 남은 콩알을 모두 한꺼번에 처리하는 공정을 채택하기로 했다. 이때 약품이나 풋콩은 특성으로 표현된 것 이외의 상호작용을 일으키지 않는다는 것을 알고 있다. 그러나 처리되지 못한 콩알이 남으면 후공정에 지장이 생기므로 이는 허용되지 않는다.

물론 설비의 수율을 높이려면 버리는 콩알이 최대한 적은 편이 좋다. ICPC 사의 소프트웨어 엔지니어인 당신의 일은, 처리액에 쓰는 약품의 종류를 알맞게 골라 최대한 많은 콩알을 쓸 수 있도록 계획하는 프로그램을 작성하는 것이다.

예를 들어, 입출력 예의 첫 번째 데이터 세트에서는 종류 1과 2의 약품을 혼합한 처리액을 쓰면 1번째부터 3번째까지의 콩알을 처리할 수 있다. 그러나 종류 1과 2의 약품을 각각 쓰거나 쓰지 않는 총 4가지 처리액 중 어느 것으로도 어떤 한 콩알은 처리할 수 없다. 따라서 이 데이터 세트의 답은 3이다. 두 번째 데이터 세트에 있는 것처럼, 한 콩알이 같은 특성을 중복해서 지닐 수도 있으니 주의하라. 이 경우도 둘 중 어느 한 조건을 충족하면 처리할 수 있다. 세 번째 데이터 세트에서는 어느 약품도 쓰지 않은 처리액을 쓰면 모든 콩알을 처리할 수 있다.

입력은 50개 이하의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.

N M
a1 b1
...
aM bM

첫 줄에는 약품의 종류 수 N (1 ≤ N ≤ 2000)과 풋콩에 들어 있는 알 수 M (1 ≤ M ≤ 2000)이 이 순서로 주어진다. 이어지는 M줄에 콩알에 관한 정보가 한 줄씩 주어진다. 1 + i번째 줄에는 끝에서 세어 i번째 콩알의 특성을 나타내는 두 정수 ai와 bi가 주어진다. 이 정수를 x라고 하면 -N ≤ x ≤ N, x ≠ 0을 만족하고, x가 양수일 때는 i번째 콩알이 종류 x의 약품으로 처리할 수 있음, 즉 특성 P(x)를 지님을, x가 음수일 때는 i번째 콩알이 종류 |x|의 약품을 쓰지 않으면 처리할 수 있음, 즉 특성 Q(|x|)를 지님을 각각 뜻한다.

입력의 끝은 두 개의 0으로 이루어진 줄로 나타낸다.

각 데이터 세트에 대해, 처리에 사용할 수 있는 콩알의 최대 개수를 한 줄에 출력하라.