뮤텍스

현대 프로그래밍 언어에서는 하나의 프로그램이 여러 개의 실행 스레드를 동시에 가질 수 있습니다. 이는 마치 여러 프로그램이 같은 주소 공간에서 병렬로 실행되면서 같은 변수들을 함께 읽고 쓰는 것과 같습니다. 스레드들은 종종 서로 동기화되어야 합니다. 예를 들어 한 스레드가 다른 스레드의 계산이 끝나고 그 결과가 어떤 변수에 저장될 때까지 기다려야 할 수 있습니다.

가장 단순한 동기화 도구는 뮤텍스(mutex)입니다. 뮤텍스는 잠김(locked) 또는 풀림(unlocked) 상태를 가지는 객체입니다. 잠긴 뮤텍스는 정확히 하나의 스레드가 소유합니다. 스레드는 뮤텍스에 대해 LOCK과 UNLOCK 두 가지 연산을 수행할 수 있습니다.

• 스레드가 현재 풀려 있는 뮤텍스에 LOCK을 수행하면, 그 뮤텍스는 잠기고 그 스레드가 소유자가 됩니다.
• 스레드가 이미 다른 스레드가 잠근 뮤텍스에 LOCK을 수행하면, 그 뮤텍스가 풀릴 때까지 그 스레드는 대기(block) 상태가 됩니다.
• 스레드가 자신이 소유한 뮤텍스에 UNLOCK을 수행하면 그 뮤텍스는 풀립니다. 그 뮤텍스를 LOCK하려고 기다리던 다른 스레드가 있었다면, 그중 하나(임의로 선택)가 소유권을 얻습니다.

교착 상태(deadlock)는 스레드들이 더 이상 어떤 진행도 할 수 없게 될 때 발생합니다. 즉, 아직 끝나지 않은 모든 스레드가 다른 스레드가 소유한 뮤텍스를 LOCK하려다 막혀 있는 상태입니다. 여기에는 어떤 스레드가, 뮤텍스를 잠근 채 UNLOCK하지 않고 종료해 버린 다른 스레드 때문에 영원히 기다리게 되는 경우도 포함됩니다.

각 스레드는 다음 형태의 명령어들이 고정된 순서로 나열된 것입니다:

LOCK <mutex>UNLOCK <mutex>

다음을 가정할 수 있습니다:

• 뮤텍스 이름은 하나의 대문자 A...Z 입니다;
• 어떤 스레드도 이미 자신이 소유한 뮤텍스를 다시 LOCK하지 않습니다;
• 어떤 스레드도 자신이 소유하지 않은 뮤텍스를 UNLOCK하지 않습니다.

주어진 스레드들에 대해, 이들의 실행을 어떤 순서로 교차 실행하더라도 완전한 교착 상태에 도달할 수 있는지를 판정하세요. 완전한 교착 상태란, 적어도 하나의 스레드가 아직 끝나지 않았고 끝나지 않은 모든 스레드가 LOCK에서 막혀 있는, 도달 가능한 상태를 말합니다.

첫째 줄에 스레드의 개수 M (1 ≤ M ≤ 5)이 주어집니다. 이어서 M개의 스레드 설명이 주어집니다. 각 설명의 첫 줄에는 그 스레드의 명령어 개수 N_i (1 ≤ N_i ≤ 10)가 주어지고, 그 다음 N_i개의 줄에 각각 하나의 명령어가 불필요한 공백 없이 주어집니다.

첫째 줄에 D를 출력합니다. 완전한 교착 상태에 도달할 수 있으면 1을, 그렇지 않으면 0을 출력합니다.

D = 1이면 둘째 줄에 도달 가능한 교착 상태 중 사전순으로 가장 작은 것을 출력합니다. 상태는 각 스레드에 대해(입력에 주어진 순서대로) 그 스레드가 현재 멈춰 있는 명령어의 0부터 시작하는 인덱스를, 이미 종료된 스레드라면 -1을 나열하여 나타냅니다. 값들은 하나의 공백으로 구분합니다. 상태들은 이렇게 출력되는 정수 수열로 비교하며(따라서 종료를 뜻하는 -1은 모든 음이 아닌 인덱스보다 앞서며), 그중 사전순으로 가장 작은 수열을 출력해야 합니다.

D = 0이면 첫째 줄 외에는 아무것도 출력하지 않습니다.