시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 40 18 14 46.667%

문제

악명높은 의사 House는 환자를 치료할 때 죽을 환자는 버리고 살 환자는 살린다. 중상을 입어 거의 죽을 고비에 다다른 환자만이 그에게 맡겨지는데, 이러한 환자에게서는 여러 가지 증세가 동시에 관측되곤 한다.

House에게는 이러한 증세들 중 두 가지가 동시에 관측될 때면 환자가 죽게 된다는 규칙을 정리해 둔 표가 있다. 이를테면, 뇌출혈과 복막염이 동시에 관측되면 그 환자는 죽에 되고, 뇌출혈이 일어나지 않고 불면증이 발생하게 되어도 그 환자는 죽게 된다는 등이다.

그런데 최근 House의 손에 맡겨진 환자가 너무 많이 죽어나가는 바람에, House의 규칙이 너무 가혹해서 과연 House에게 맡겨져서 살아남을 수 있는 환자가 있을 수 있는지를 검사해야 할 필요가 생겼다.

House의 규칙이 주어지면, 이러한 규칙에 의거해서 과연 살아남을 수 있는 환자가 존재하는지, 아니면 이 규칙에 따르면 모든 환자가 죽을 수밖에 없는지를 알아내는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 데이터들로 구성되어 있다. 각 데이터의 첫 줄에는 House의 규칙의 개수 N, 증세의 종류 M이 빈 칸을 사이에 두고 주어진다. 다음 줄부터 N개의 줄에 걸쳐 House의 규칙에 대한 정보가 주어진다. 규칙은 두 개의 수로 표현되는데, 각 수가 증세를 나타내는 것이다. 증세의 절대값은 1 이상 M 이하이며, 증세가 음수인 경우는 그 증세가 일어나지 않는다는 것을 의미한다. (N≤200,000, M≤20,000)

예를 들어 House의 규칙이 2 -3이라면, 증세 2가 일어나고 동시에 증세 3이 일어나지 않은 경우 환자가 죽게 된다는 뜻이다. 

데이터의 끝은 0 0으로 주어진다. 즉 N과 M이 0으로 주어지면 입력을 종료하면 된다.

출력

첫째 줄부터 각 테스트 데이터마다 한 줄에 규칙에서 살아남을 수 있는 사람이 있으면 1을, 살아남는 게 불가능한 경우 0을 출력한다.

예제 입력

3 3
1 -2
2 3
-3 -1
4 2
1 2
1 -2
-1 2
-1 -2
0 0

예제 출력

1
0

힌트

출처