Mutexes

Time limit1sMemory limit128 MB

Summary

Given up to 5 threads each executing LOCK/UNLOCK instructions on mutexes, determine if a deadlock state is reachable via some interleaving and if so output the lexicographically smallest deadlock state description.

Level: Medium7 of 10
Topics: BFS, Simulation, Backtracking, Graph
Solved: No attempts yet

Problem

Modern programming languages let a single program run several threads of execution at once. It is as if several programs were running in parallel within the same address space, reading and writing the same variables. Threads often need to synchronize with one another. For example, one thread may need to wait until another finishes some computation and stores its result into a variable.

The simplest synchronization tool is a mutex. A mutex is an object that is either locked or unlocked. A locked mutex is owned by exactly one thread. A thread can apply two operations to a mutex: LOCK and UNLOCK.

When a thread applies LOCK to a mutex that is currently unlocked, the mutex becomes locked and the thread becomes its owner.
When a thread applies LOCK to a mutex that is already locked by another thread, the thread is blocked until the mutex is unlocked.
When a thread applies UNLOCK to a mutex it owns, the mutex becomes unlocked. If other threads were waiting to LOCK it, one of them (chosen arbitrarily) becomes the new owner.

A deadlock occurs when a group of threads can no longer make any progress: every thread that has not finished is blocked while trying to LOCK a mutex owned by some other thread. This includes the case where a thread waits for a mutex that was locked by another thread which then terminated without unlocking it.

Each thread is a fixed sequence of instructions of the form:

LOCK <mutex>
UNLOCK <mutex>

You may assume the following:

mutex names are single uppercase letters A...Z;
no thread ever locks a mutex it already owns;
no thread ever unlocks a mutex it does not own.

Given the threads, decide whether some interleaving of their executions can reach a complete deadlock: a reachable state in which at least one thread has not finished and every unfinished thread is blocked on a LOCK.

Input

The first line contains the number of threads M (1 ≤ M ≤ 5). Then follow M thread descriptions. Each description begins with a line containing the number of instructions N_i (1 ≤ N_i ≤ 10) in that thread, followed by N_i lines, each holding a single instruction with no extraneous whitespace.

Output

On the first line print D: 1 if a complete deadlock is reachable, or 0 otherwise.

If D = 1, on the second line print the lexicographically smallest reachable deadlock state. Describe a state by listing, for each thread in input order, the zero-based index of the instruction it is currently stopped at, or -1 if the thread has already terminated. Separate the values with single spaces. States are compared as these printed integer sequences (so -1, meaning a terminated thread, sorts before every non-negative index), and you must print the smallest such sequence.

If D = 0, print nothing after the first line.

Examples3

Example 1
Input
```
2
1
LOCK X
2
LOCK Y
LOCK X
```
Expected output
```
1
-1 1
```
Example 2
Input
```
1
2
LOCK A
UNLOCK A
```
Expected output
```
0
```

Example 3

Input

2
4
LOCK A
LOCK B
UNLOCK B
UNLOCK A
4
LOCK B
LOCK A
UNLOCK A
UNLOCK B

Expected output

1
1 1