시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 62 9 5 31.250%

문제

수십년간 소프트웨어 엔지니어로 일해온 백승환은 이제 전혀 다른 일을 시작하기로 했다. 승환이는 여러가지 일자리를 살펴보고 있었고, 승환이의 눈을 사로잡은 직업이 하나 있었으니… 그것은 양식업이었다.

오늘은 승환이가 출근한 첫 날이다.

승환이의 상사 규현이는 이미 승환이가 할 일을 정해놓았다. 승환이는 저수지 하나를 다른 것들로 부터 격리시켜야 한다.다음은 승환이가 생각한 방법이다.

두 저수지는 여러개의 수로로 서로 연결되어 있다. 각 수로에는 두 개의 문이 있다. 두 문이 모두 열려있으면, 수로는 열려있는 것이고, 그렇지 않으면 닫혀있는 것이다. 문은 스위치로 작동한다 하나의 스위치는 여러개의 문을 작동시킬 수 있지만, 각각의 문은 오직 단 하나의 스위치로만 작동시킬 수 있다. 하나의 스위치로 어떤 수로의 두 문을 작동 시키는 것이나, 스위치가 작동시킬 수 있는 문이 아얘 없는 것도 가능하다

  위의 그림은 3개의 수로와 2개의 스위치가 있는 예이다.

스위치는 다음 두 가지 방법 중의 한 방법으로 문을 작동 시킨다.

  • 스위치가 켜져있으면, 문이 열려있고, 스위치가 꺼져있으면, 문이 닫혀있다.
  • 스위치가 켜져있으면, 문이 닫혀있고, 스위치가 꺼져있으면, 문이 열려있다.

  승환이는 스위치를 가지고 조금 놀다가, 지금까지 수십년간 일해온 프로그래밍 스킬을 여기에 적용시킬 수 있다는 사실을 알았다. 문과 스위치간의 연결 설정이 주어졌을 때, 모든 수로를 닫는 것이 가능한지 구하는 프로그램을 작성하시오. 만약, 가능하다면, 각 스위치가 켜져야하는지, 꺼져야하는지, 상태를 출력한다.

입력

첫째 줄에 수로의 개수 N (1<=N<=250,000)과 스위치의 개수 M (1<=M<=500,000)이 주어진다. 둘째 줄부터 N개의 줄에 각 수로의 정보가 주어진다. 수로의 정보는 4개의 숫자로 이루어져 있고, a, sa, b, sb라고 한다. a와 b (1<=a,b<=m)은 연결되어 문을 작동시키는 스위치이다. sa와 sb는 0과 1 중의 하나이다. si가 0이면, 스위치 i가 꺼져야 문이 닫히는 것이고, si가 1이면, 스위치 i가 켜져야 문이 닫히는 것이다.

출력

모든 수로를 닫는 것이 가능하면, m개의 줄에, 각 스위치가 꺼져야 하면 0을, 켜져야 하면 1을 출력한다. 여러가지가 있으면, 아무거나 출력해도 된다.

모든 수로를 닫는 것이 불가능하다면, IMPOSSIBLE을 출력한다.

예제 입력

3 2
1 0 2 1
1 0 2 0
1 1 2 1

예제 출력

0
1

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 3번