Beyond the Void

#include <iostream>
 
using namespace std;
 
class tSet
{
	public:
		unsigned int P;
		tSet():P(0){}
		bool Contain(int k)
		{
			return (P >> (k))&1;
		}
		void Union(tSet &k)
		{
			P |=k.P;
		}
		void Union(int k)
		{
			P |=1 << (k);
		}
};
 
const int Target='S'-'A';
const int MAX_L=101;
const int INF=0x7FFFFFF;
 
int N,M,L,Ans;
 
char S[MAX_L];
tSet H[26][26];
tSet G[MAX_L][MAX_L];
int F[MAX_L][MAX_L];
 
void init()
{
	int i,c,a,b;
	freopen("gen.in","r",stdin);
	freopen("gen.out","w",stdout);
	scanf("%dn",&M);
	for (i=1;i<=M;i++)
	{
		gets(S);
		c=S[0]-'A';
		a=S[1]-'A';
		b=S[2]-'A';
		H[a][b].Union(c);
	}
	scanf("%dn",&N);
}
 
void solve()
{
	int i,j,k,a,b;
	for (i=1;i<=L;i++)
	{
		for (j=1;j<=L;j++)
		{
			G[i][j].P=0;
		}
		G[i][i].Union((int)S[i-1]);
	}
	for (i=L;i>=1;i--)
	{
		for (j=i+1;j<=L;j++)
		{
			for (k=i;k<=j-1;k++)
			{
				for (a=0;a<26;a++)
				{
					for (b=0;b<26;b++)
					{
						if (G[i][k].Contain(a) && G[k+1][j].Contain(b))
						{
							G[i][j].Union(H[a][b]);
						}
					}
				}
			}
		}
	}
 
	for (i=1;i<=L;i++)
	{
		for (j=1;j<=L;j++)
		{
			F[i][j]=INF;
		}
	}
 
	for (i=L;i>=1;i--)
	{
		for (j=i;j<=L;j++)
		{
			if (G[i][j].Contain(Target))
			{
				F[i][j]=1;
			}
			else
			{
				for (k=i;k<=j-1;k++)
				{
					if (F[i][k]+F[k+1][j]<F[i][j])
					{
						F[i][j]=F[i][k]+F[k+1][j];
					}
				}
			}
		}
	}
 
	Ans=F[1][L];
}
 
int main()
{
	init();
	for (int i=1;i<=N;i++)
	{
		gets(S);
		for (L=0;S[L];L++)
		{
			S[L]-='A';
		}
		solve();
		if (Ans==INF)
			printf("NIEn");
		else
			printf("%dn",Ans);
	}
	return 0;
}