Deadlock Detection in Multithreaded Mutex Operations

Modern programming languages allow the creation of multi-threaded programs in which several threads run concurrently in the same address space and access shared variables. Often, threads need to synchronize with each other. For example, one thread may need to wait for another to finish a calculation and store the result in a shared variable.

The simplest synchronization primitive is a mutex. A mutex is a special object that can be either locked or unlocked. A locked mutex is always owned by exactly one thread. Threads perform two operations on mutexes:

• LOCK <mutex>
• UNLOCK <mutex>

If a thread issues a LOCK command on an unlocked mutex, the mutex becomes locked and that thread takes ownership. If a thread attempts to lock a mutex that is already locked by another thread, the requesting thread will be blocked until the mutex is unlocked. When a thread executes an UNLOCK command on a mutex it owns, the mutex is released (becomes unlocked). If other threads are waiting to lock that mutex, one of them is chosen arbitrarily to become the new owner.

A common problem in multi-threaded programming is deadlock. Deadlock arises when two or more threads are waiting for mutexes held by each other, making none able to continue execution. Deadlock can also occur if a thread that holds a mutex terminates without releasing it, causing other threads waiting for that mutex to be blocked indefinitely.

You are given descriptions of several threads. Each thread consists of a sequence of instructions, each being one of the following:

LOCK <mutex>
UNLOCK <mutex>

The following assumptions hold:

• Mutex names are uppercase letters from A to Z.
• No thread will attempt to lock a mutex it already owns.
• No thread will attempt to unlock a mutex that it does not currently own.

Your task is to determine whether a deadlock will occur when all the threads execute concurrently. For the purpose of this problem, use the following simulation strategy:

All threads start at the beginning of their instruction sequences. At each step, if any thread can safely execute its next instruction (that is, a LOCK command only if the mutex is free, or an UNLOCK command), then execute that instruction. If no thread can proceed and not all threads have finished executing their instructions, then a deadlock has occurred. Otherwise, if all threads finish their instructions, the execution is safe.

Note that if a thread terminates while holding a mutex, that mutex remains locked forever.

inputFormat

The input begins with an integer n ( 1 ≤ n ≤ 26), the number of threads. Then for each thread, there is a block of instructions. For each thread:

• The first line contains an integer m (the number of instructions in this thread).
• The next m lines each contain an instruction in the format described above.

It is guaranteed that each mutex name is a single uppercase English letter.

outputFormat

Output a single line containing either safe if all threads can complete their instruction sequences without deadlock, or deadlock if a deadlock occurs.

sample

2
2
LOCK A
UNLOCK A
2
LOCK A
UNLOCK A

safe