問題文
並行処理環境におけるデッドロックとは， 複数のスレッドがお互いにいくつかの資源を使い終わるのを待っていて先に進めないという望ましくない状況を指す． あなたには， 与えられた命令列を複数のスレッドが並行に実行したときにデッドロックが発生する可能性があるか否かを判定するプログラムを作って欲しい．
命令列は '
数字の命令 k は L0 から L9
まで 10 個あるロックと呼ばれる共有資源のうち Lk
を獲得する命令である．
あるスレッドが Lk を獲得すると，
同じスレッドが '
より厳密に記述すると，全てのスレッドが終了するまで，以下の処理が繰り返される．
- まだ終了していないスレッドがひとつ任意に選ばれる．
- 選ばれたスレッドの次のまだ実行していない命令を実行しようと試みる．
- 次の命令が数字 k であり， ロック Lk がどのスレッドにも保持されていないならば， そのスレッドは命令 k を実行し，ロック Lk を獲得する．
- 次の命令が数字 k であり， ロック Lk が既にどれかのスレッドに保持されていれば， 命令 k は実行されない．
- 次の命令が '
u ' であるとき， 命令 'u ' を実行し，そのスレッドが保持していたロックをすべて解放する．
このように実行を進めていくと， まだ終了していないスレッドの次に実行する命令が全て， 保持されているロックの獲得命令という状態に陥ることがある． こうなると，以降どのスレッドを選んでも命令が実行されることはない． この状態をデッドロックと呼ぶ．
命令列によっては，スレッドをどのような順番で選んで実行しても決してデッドロックに陥らない． このような命令列は安全であるという． そうでない場合，言い換えるとひとつ以上の実行順序でデッドロックに陥る場合， 命令列は危険であるという． あなたには， 与えられた命令列が安全であるか危険であるかを判定するプログラムを作って欲しい．
Input
入力は 50 個以下のデータセットからなる． 各データセットは次の形式で表される．
n
s
n は命令列の長さ，s は命令列を表す文字列である．
n は，正の整数であり，10,000 を超えない．
s の各文字は '
入力の終わりは，ゼロだけからなる行で表される．
Output
各データセットについて，与えられた命令列が安全ならば
Sample Input
11 01u12u0123u 6 01u10u 8 201u210u 9 01u12u20u 3 77u 12 9u8u845u954u 0
Output for the Sample Input
SAFE UNSAFE SAFE UNSAFE UNSAFE UNSAFE
2 番目の入力 "
→
→
図1: Sample Input 2 "
一方で，3 番目の入力 "