Description

Modern programming languages allow writing programs consisting of multiple execution threads. This is as if several programs run in parallel within the same address space and access the same variables. Usually, threads need to synchronize with each other. For example, one thread may need to wait for another to finish some computation and store the result in a variable.

The simplest synchronization tool is the mutex. A mutex is a special object that can be in a locked or unlocked state. A locked mutex is always owned by one thread. Threads can apply two operations to a mutex: LOCK and UNLOCK.

When a thread applies LOCK to a currently unlocked mutex, the mutex becomes locked and the thread obtains ownership of that mutex. If a thread tries to apply LOCK to a mutex that is already locked by another thread, the thread will be blocked until the mutex is unlocked.

When a thread applies UNLOCK to a mutex it owns, the mutex becomes unlocked. If there are other threads waiting to lock the mutex, one of them is granted ownership of the mutex. If multiple threads are waiting, any one is chosen.

One of the common problems in multithreaded programs is deadlock. Deadlock occurs when two or more threads are waiting for each other to release mutexes and none of them can proceed. Deadlock also occurs when a thread is waiting for a mutex locked by another thread, and that other thread has terminated without releasing the mutex.

You are given descriptions of some threads. Your task is to determine whether a deadlock can occur.

Each thread is a sequence of instructions of the following forms:

LOCK <mutex>
UNLOCK <mutex>

You may assume the following about the commands:

• Mutex names are the capital letters A$\cdots$Z.
• No thread tries to lock a mutex it already owns.
• No thread tries to unlock a mutex that does not belong to it.

Input Format

The first line contains an integer, the number of threads $M$, followed by $M$ blocks describing each thread. The first line of the block describing thread $i$ contains an integer, the number of instructions in this thread $N_i$, followed by $N_i$ lines of instructions. The instructions contain no extra spaces.

Output Format

The first line must contain an integer: $D$. If a deadlock is possible, $D$ must be $1$, otherwise $0$.

If a deadlock is possible, the second line must describe a program state in which a deadlock occurs. If there are multiple deadlock states, output any one of them. In this case, we are looking for a complete deadlock, where no thread can continue executing—threads must be terminated or blocked by a mutex. If no deadlock is possible, this line must be empty.

A program state is described by giving, for each thread in the order they appear in the input, the zero-based index of its current instruction. For a terminated thread, output $-1$ as the index. Indices must be on one line and separated by spaces.

2
1
LOCK X
2
LOCK X
LOCK Y

1
-1 1

Hint

Constraints

For $100\%$ of the testdata, $1 \le M \le 5$, $1 \le N_i \le 10$.

Scoring

The score of this problem follows the original BOI settings. The full score is $60$.

Notes

Source: Day 2: Mutexes from Baltic Olympiad in Informatics 2000. Translated and整理 (pinyin: zhengli) by @求学的企鹅。

Translated by ChatGPT 5