#include <iostream>
#include <fstream>
#include <string>
#include <unordered_map>
#include <vector>
#include <utility>

using namespace std;

bool search(const vector<pair<string,string>> &repls,const string &target,string from,int depth){
	if(from==target)return true;
	if(depth<=0)return false;
	int i,j,r,l;
	const int fromlen=from.size(),nrepls=repls.size();
	for(i=0;i<fromlen;i++){
		for(r=0;r<nrepls;r++){
			l=repls[r].first.size();
			if(fromlen-i<l)continue;
			for(j=0;j<l;j++)if(from[i+j]!=repls[r].first[j])break;
			if(j<l)continue;
			if(search(repls,
			          target,
			          from.substr(0,i)+repls[r].second+from.substr(i+repls[r].first.size()),
			          depth-1)){
				cerr<<repls[r].first<<" -> "<<repls[r].second<<" (at "<<i<<" in "<<from<<')'<<endl;
				return true;
			}
		}
	}
	return false;
}

int cheat(const vector<pair<string,string>> &repls,const string &target,string from){
	int i,r,j,l;
	int depth;
	const int fromlen=from.size(),nrepls=repls.size();
	for(depth=0;from!=target;depth++){
		for(i=0;i<fromlen;i++){
			for(r=0;r<nrepls;r++){
				l=repls[r].first.size();
				if(fromlen-i<l)continue;
				for(j=0;j<l;j++)if(from[i+j]!=repls[r].first[j])break;
				if(j<l)continue;
				from=from.substr(0,i)+repls[r].second+from.substr(i+repls[r].first.size());
				i=fromlen+41; break;
			}
		}
		if(i!=fromlen+42)return -1;
		cout<<from<<endl;
	}
	return depth;
}

int main(void){
	ifstream in("day19.txt");
	string line,target;
	int a,b;
	vector<pair<string,string>> repls;
	while(true){
		getline(in,line);
		if(line.size()==0){
			getline(in,target);
			break;
		}
		if(!in)break;
		a=line.find(' ');
		b=line.find(' ',a+1);
		// repls.emplace_back(line.substr(0,a),line.substr(b+1));
		repls.emplace_back(line.substr(b+1),line.substr(0,a)); //reversed
	}

	// repls={{"H","HO"},{"H","OH"},{"O","HH"},{"e","O"},{"e","H"}};
	// repls={{"HO","H"},{"OH","H"},{"HH","O"},{"O","e"},{"H","e"}}; //reversed
	// target="HOHOHO";

	//for(const pair<string,string> &p : repls)cout<<"repl: "<<p.first<<" -> "<<p.second<<endl;
	//cout<<"target: "<<target<<endl;

	cout<<cheat(repls,"e",target)<<endl;

	int depth;
	for(depth=1;;depth++){
		cerr<<"Starting depth "<<depth<<"..."<<endl;
		// const bool res=search(repls,target,"e",depth);
		const bool res=search(repls,"e",target,depth); //reversed
		if(res)break;
	}
	cout<<depth<<endl;
}