플래티넘 IV어느 행성에 \(N\)개의 전초기지가 있다. 각 전초기지는 두 진영 중 하나에 배속되어야 한다. 진영은 \(0\)번(연합)과 \(1\)번(자치)으로 나뉜다.
그런데 정치적 사정으로 \(M\)개의 금지 규칙이 있다. 각 규칙은 네 정수 \(i, a, j, b\)로 주어지며, '전초기지 \(i\)가 진영 \(a\)에 속하고 동시에 전초기지 \(j\)가 진영 \(b\)에 속하는' 배치는 허용되지 않는다는 뜻이다. (즉 그 조합만 금지되며, 둘 중 하나라도 다른 진영이면 괜찮다.)
모든 금지 규칙을 위반하지 않는 진영 배치가 존재하는지 판정하고, 존재한다면 그러한 배치를 하나 출력하여라.
\(1 \le N \le 100{,}000\)
\(1 \le M \le 300{,}000\)
\(0 \le i, j \le N-1\)
\(a, b \in \{0, 1\}\)
첫 줄에 전초기지의 수 \(N\)과 금지 규칙의 수 \(M\)이 주어진다. 전초기지는 \(0\)부터 \(N-1\)까지 번호가 매겨져 있다.
다음 \(M\)개의 줄에 각각 네 정수 \(i\), \(a\), \(j\), \(b\)가 주어진다 (\(0 \le i, j \le N-1\), \(a, b \in \{0, 1\}\)). 이는 '\(i\)가 진영 \(a\)이면서 동시에 \(j\)가 진영 \(b\)인' 배치가 금지됨을 의미한다. \(i = j\)인 규칙도 주어질 수 있다.
조건을 만족하는 배치가 존재하면 첫 줄에 POSSIBLE을 출력하고, 둘째 줄에 각 전초기지의 진영 번호(\(0\) 또는 \(1\))를 공백으로 구분해 \(N\)개 출력한다. 가능한 배치가 여러 가지면 그 중 아무거나 출력하면 된다. 존재하지 않으면 한 줄에 IMPOSSIBLE을 출력한다.
3 2
0 1 1 1
0 0 2 0
POSSIBLE
0 0 1규칙은 '0이 진영 1이고 1도 진영 1'인 배치 금지, '0이 진영 0이고 2도 진영 0'인 배치 금지이다. 배치 \(0\ 0\ 1\) 은 첫 규칙(0이 진영0이라 무관)도, 둘째 규칙(2가 진영1이라 무관)도 어기지 않으므로 한 해가 된다. (다른 유효한 배치도 정답으로 인정된다.)
1 2
0 0 0 0
0 1 0 1
IMPOSSIBLE첫 규칙은 '0이 진영 0'을 금지하므로 0은 진영 1이어야 하고, 둘째 규칙은 '0이 진영 1'을 금지하므로 0은 진영 0이어야 한다. 두 요구가 모순이므로 IMPOSSIBLE이다.
레이팅 미적용riseoj 작성
출처 Original
