aoj1604.cpp

aoj1604.cpp

#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace atcoder;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
 
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
 
#define MOD 1000000007
 
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
const double EPS = 1e-8, PI = acos(-1);
const double pi = 3.141592653589793238462643383279;

bool dp[10][10][(1<<10)];
int main() {  
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);

  int n;
  while(cin >> n, n) {
    string s; cin >> s;
    bool ok = true;
    REP(i,10) REP(j,10) REP(k,(1<<10)) dp[i][j][k] = false;
    REP(i,10) dp[i][i][(1<<i)] = true; 
    REP(i,n) {
      if(!ok) break;
      int j = i;
      while(j<n && s[j] != 'u') j++;
      int mask = 0;
      for(int k=i; k<j-1; k++) {
        if(!ok) break;
        int u = s[k]-'0', v = s[k+1]-'0';

        for(int l=0; l<10; l++) {
          for(int bit=0; bit<(1<<10); bit++) {
            if((mask & bit) != 0) continue;
            
            dp[l][v][bit | mask | (1<<v)] |= dp[l][u][bit];
            if(l == v && dp[l][u][bit]) ok = false;
          } 
        }
        if(mask >> u & 1) ok = false;
        mask |= (1<<u);
      }
      i = j;  
    }
    cout << (ok?"SAFE":"UNSAFE") << '\n';
  }
  return 0;
}