code

//洛谷P1028.cpp
#include<iostream>
#include<vector>
using namespace std;
int all=1;
string n;
int k,len;
void dfs(int now,string &tmp,vector<vector<char>> &l,int x){
	if(now==k)return;
	char w;int ans=0;
    for(int i=x;i<len;i++){
    	for(int j=0;j<k;j++){
    		if(tmp[i]==l[j][0]){
    			ans++;all++;
    			w=tmp[i];
    			tmp[i]=l[j][1];
    			cout<<tmp<<endl;
	   			dfs(now+1,tmp,l,i);
    			tmp[i]=w;
			}
		}
	}
}
int main(){
    cin>>n>>k;
    len=n.size();
    vector<vector<char>> l(k,vector<char>(2,'0'));
    for(int i=0;i<k;i++)cin>>l[i][0]>>l[i][1];
    dfs(0,n,l,0);
    cout<<all;
    return 0;
}