#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
bool st[N]; //标记某个数有没有出现过 
int a[N],b[N];
int main()
{
    int n,k;
    cin>>n>>k;
    queue<int> q;
    q.push(n); //起点入队 
    st[n]=1;
    int cnt=1; //不同的数的个数 
    for(int i=1;i<=k;i++)
    {
        cin>>a[i]>>b[i];
    } 
    while(q.size()) //如果元素还没有扩展完就一直扩展 
    {
        int t=q.front();
        q.pop();
        int tx=t; //临时元素 
        int p=1; //当前位置的权重 
        while(tx)
        {
            int ge=tx%10; //当前各位 
            tx/=10; //删除当前个位 
            for(int i=1;i<=k;i++) //枚举规则 
            {
                if(a[i]==ge) //符合规则 
                {
                    int cur=t+(b[i]-a[i])*p; //计算t由第i个规则可以得到的元素 
                    if(st[cur]==0) //当前元素还没有扩展 
                    {
                        q.push(cur); //加入待扩展元素 
                        st[cur]=1;
                        cnt++; //元素增加一个 
                    }
                }
            }
            p=p*10; //下一位的权重 
        }
    }
    cout<<cnt;
    return 0;
}