#include <cstdio> #include <set> #include <map> #include <string> #include <iostream> #include <queue> std::set<std::pair<std::string, std::string>> zheng, fan; std::string s, t; std::string a, b; std::map<std::string, int> vis[2]; std::queue<std::pair<std::string, int>> q; int main() { std::cin >> s >> t; while((std::cin >> a >> b)) { zheng.insert(std::make_pair(a, b)); fan.insert(std::make_pair(b, a)); } q.push(std::make_pair(s, 1)); while(!q.empty()) { if(q.front().second >= 7) {q.pop(); continue;} if(vis[0][q.front().first] != 0) {q.pop(); continue;} vis[0][q.front().first] = q.front().second; // printf("正："); // std::cout << q.front().first; // printf(", %d\n", q.front().second); for(int i = 0; i < q.front().first.length(); i++) { for(int j = 1; j <= q.front().first.length() - i; j++) { for(auto it : zheng) { if(it.first == q.front().first.substr(i, j)) { q.push({q.front().first.substr(0, i) + it.second + q.front().first.substr(i + j), q.front().second + 1}); } } } } q.pop(); } q.push(std::make_pair(t, 1)); while(!q.empty()) { if(q.front().second >= 7) {q.pop(); continue;} if(vis[1][q.front().first] != 0) {q.pop(); continue;} if(vis[0][q.front().first] != 0) { printf("%d", vis[0][q.front().first] + q.front().second - 2); return 0; } vis[1][q.front().first] = q.front().second; // printf("反："); // std::cout << q.front().first; // printf(", %d\n", q.front().second); for(int i = 0; i < q.front().first.length(); i++) { for(int j = 1; j <= q.front().first.length() - i; j++) { for(auto it : fan) { if(it.first == q.front().first.substr(i, j)) { q.push({q.front().first.substr(0, i) + it.second + q.front().first.substr(i + j), q.front().second + 1}); } } } } q.pop(); } puts("NO ANSWER!"); return 0; }