代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

map<char, vector<char> >m;// 匹配：a能去往多个b
map<string, bool>u;
string n;
int k;

ll dfs(string st)
{
	u[st]=1;
	ll sum=0;
	int len=st.length();
	for(int i=0;i<len;i++)
	{
		char ch=st[i];
		int vlen=m[ch].size();
		for(int j=0;j<vlen;j++)
		{
			string ts=st;
			ts[i]=m[ch][j];
			if(u[ts]) continue;// 剪枝
			sum+=dfs(ts);
		}
	}
	return sum+1;
}

int main()
{
	cin>>n>>k;
	char a, b;
	for(int i=1;i<=k;i++)
	{
		cin>>a>>b;
		m[a].push_back(b);
	}
	ll ans=dfs(n);
	cout<<ans;
	return 0;
}

#3MLE #4#5TLE

dfs搜爆了求优化