시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 69 22 18 46.154%

문제

악명높은 의사 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을 출력한다.

예제 입력 1

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

예제 출력 1

1
0

출처

  • 문제를 만든 사람: author5
  • 문제의 오타를 찾은 사람: jh05013