int extend(queue<string>& q,unordered_map<string,int>& da,unordered_map<string,int>& db,string a[],string b[]) {
	string t = q.front();
	q.pop();
	for(int i = 0;i < q.size();i ++) {
		for(int j = 0;j < n;j ++) {
			if(t.substr(i,a[j].size()) == a[j]) {
				string state = t.substr(0,i) + b[j] + t.substr(i + a[j].size());
				if(db.count(state)) return da[t] + 1 + db[state];
				if(da.count(state)) continue;
				da[state] = da[t] + 1;
				q.push(state);
			}
		}
	}
	return 11;
}