Deadlock Detection

In a concurrent environment, a deadlock is a state where two or more threads wait for each other to release resources and none of them can make progress. Given an instruction sequence that several threads run at the same time, decide whether a deadlock can happen.

The instruction sequence consists of the character u and the digits 0 to 9, and each character is one instruction. Ten threads run the same single instruction sequence. Every thread starts at the beginning of the sequence and follows it in the given order until it has executed every instruction.

All threads share ten locks, L0 to L9. A digit $k$ is the instruction that acquires lock L$k$. Once a thread acquires L$k$, it keeps that lock until the instruction u releases it. While a lock is kept, no thread can newly acquire the same lock L$k$, not even the thread that already acquired it.

Precisely, the following steps repeat until every thread has finished.

1. Choose one thread that has not finished yet, arbitrarily.
2. The chosen thread tries to execute its next instruction that is not executed yet.
   • If the next instruction is a digit $k$ and no thread keeps L$k$, the thread executes instruction $k$ and acquires L$k$.
   • If the next instruction is a digit $k$ and some thread already keeps L$k$, instruction $k$ is not executed.
   • If the next instruction is u, the thread executes it and releases every lock it keeps.

After several steps the run can fall into a state where the next instruction of every unfinished thread acquires a lock that is already kept. Once that state happens, no instruction is ever executed again, whichever thread is chosen. That state is a deadlock.

Some instruction sequences never reach a deadlock, whatever the execution order is. Such a sequence is safe. Otherwise, if one or more execution orders lead to a deadlock, the sequence is unsafe. Write a program that decides whether the given instruction sequence is safe.

The input has at most 50 datasets, each in the following format.

n
s

$n$ is the length of the instruction sequence and $s$ is the string that holds the sequence. $n$ is a positive integer not greater than 10,000. Each character of $s$ is a digit from 0 to 9 or u, and $s$ always ends with u.

A line holding a single zero marks the end of the input.

For each dataset, print SAFE on its own line if the instruction sequence is safe, and UNSAFE if it is unsafe.

The sequence 01u10u can reach a deadlock. After one thread has executed the first four instructions 01u1, that thread keeps only the lock L1. If another thread executes the first instruction 0 at this point, that thread acquires L0. The first thread then tries to acquire L0, which the second thread keeps, while the second thread tries to acquire L1, which the first thread keeps. That is a deadlock.

→ →

Figure 1. Why 01u10u is unsafe.

The sequence 201u210u, on the other hand, is safe. One thread running up to 201u21 and another up to 20 looks like a deadlock, but it can never happen because no two threads can keep L2 at the same time.