记录编号	121628	评测结果	AAAAAAAA
题目名称	[NOIP 2002]字串变换	最终得分	100
用户昵称	sbit	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-09-20 19:31:56	内存使用	0.31 MiB

#include <bits/stdc++.h>
using namespace std;
namespace my_useful_tools {
#define rep(_i, _k, _j) for(int _i = _k; _i <= _j; ++_i)
#define foreach(_i, _s) for(typeof(_s.begin()) _i = _s.begin(); _i != _s.end(); ++_i)
#define upu(_a, _b) if(_a < _b) { _a = _b; }
#define upd(_a, _b) if(_b < _a) { _a = _b; }
#define pb push_back
#define mp make_pair
#define i_pair pair<int, int>
#define i_vec vector<int>
#define clr(t) memset(t, 0, sizeof t)
#define pse(t, v) memset(t, v, sizeof t)
#define brl puts("")
	const int INF = 0x3f3f3f3f;
	typedef long long LL;
	typedef double DB;
	inline void pc(char c) { putchar(c); }
	inline void R(int &t) { scanf("%d", &t); }
	inline void R(int &t1, int &t2) { scanf("%d%d", &t1, &t2); }
	inline void R(int &t1, int &t2, int &t3) { scanf("%d%d%d", &t1, &t2, &t3); }
	inline void R(LL &t) { scanf("%lld", &t); }
	inline void R(LL &t1, LL &t2) { scanf("%lld%lld", &t1, &t2); }
	inline void W(int t) { printf("%d\n", t); }
	inline void WB(int t) { printf("%d ", t); }
	inline void W(int t1, int t2) { printf("%d %d\n", t1, t2); }
	inline void W(LL t) { printf("%lld\n", t); }
	template<class T> inline void FR(T &ret, char c = ' ') {
		for(c = getchar(); c < '0' || '9' < c; c = getchar());
		for(ret = 0; '0' <= c && c <= '9'; c = getchar()) {
			ret = ret * 10 + c - '0';
		}
	}
	inline char gchar() {
		char ret = getchar();
		for(; ret == '\n' || ret == '\r' || ret == ' '; ret = getchar());
		return ret;
	}
	template<class T> inline T gcd(T a, T b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	template<class T> inline T fast_pow(T base, T index, T mod = 2147483647, T ret = 1) {
		for(; index; index >>= 1, base = base * base % mod) {
			if(index & 1) ret = ret * base % mod;
		}
		return ret;
	}
	const int maxv = 100;
	const int maxe = 100;
	struct Edge {
		int edge;
		int head[maxv], to[maxe], next[maxe];
		Edge() {
			edge = 0;
			memset(head, -1, sizeof head);
		}
		void addedge(int u, int v) {
			to[edge] = v;
			next[edge] = head[u];
			head[u] = edge++;
		}
	};
};
using namespace my_useful_tools;

string A, B, a, b;
vector<pair<string, string> > g;

int main() {
	freopen("string.in", "r", stdin); freopen("string.out", "w", stdout);
	cin >> A >> B;
	while(cin >> a >> b) {
		g.pb(mp(a, b));
	}
	set<string> vis, pis;
	map<string, int> show_v, show_p;
	queue<pair<string, int> > Q, P;
	Q.push(mp(A, 0));
	P.push(mp(B, 0));
	while(!Q.empty() && !P.empty()) {
		string t = Q.front().first;
		int step = Q.front().second;
		Q.pop();
		string u = P.front().first;
		int ptep = P.front().second;
		P.pop();
		if(pis.find(t) != pis.end()) {
			printf("%d\n", step + show_p[t]);
			return 0;
		} else if(vis.find(u) != vis.end()) {
			printf("%d\n", ptep + show_v[u]);
			return 0;
		}
		for(int i = 0, sz = g.size(); i < sz; ++i) {
			int pos = 0;
			while(t.find(g[i].first, pos) != string::npos) {
				string tmp = t;
				tmp.replace(t.find(g[i].first, pos), g[i].first.length(), g[i].second);
				if(vis.find(tmp) == vis.end()) {
					vis.insert(tmp);
					show_v[tmp] = step + 1;
					Q.push(mp(tmp, step + 1));
				}
				pos += 1;
			}
		}
		for(int i = 0, sz = g.size(); i < sz; ++i) {
			int pos = 0;
			while(u.find(g[i].second, pos) != string::npos) {
				string tmp = u;
				tmp.replace(u.find(g[i].second, pos), g[i].second.length(), g[i].first);
				if(pis.find(tmp) == pis.end()) {
					pis.insert(tmp);
					show_p[tmp] = ptep + 1;
					P.push(mp(tmp, ptep + 1));
				}
				pos += 1;
			}
		}
	}
	cout << "NO ANSWER!" << endl;

	return 0;
}