直接 dfs 或者 bfs 即可。

给出 $k$ 中变化方案，很容易发现，仅当 $x\ne y$ 的时候才对答案有贡献。

用 $a_x$ 表示 $x$ 可以变化成 $a_x$，当然，$a_x$ 可能不止一个，所以可以开个二维数组或者 vector。

这题的 bfs 用字符串存储 $n$ 更方便。

bfs 时，遍历字符串的长度，如果可以改变，就用 $nxt$ 存储改变后的字符串，如果说 $nxt$ 没有出现过，就入队，对答案的贡献增加 $1$。

由于是字符串，所以需要开个 $map$：map <string , bool > mp。

代码如下；

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

#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define rrep(i,x,y) for(int i=x;i>=y;i--)
#define sc scanf
#define pr printf
#define max(a,b) a>b?a:b
#define endline pr("\n")
inline int read(){int s=0,w=1;char c=getchar();while(!isdigit(c)){if(c=='-') w=-1;c=getchar();}while(isdigit(c)){s=(s<<1)+(s<<3)+(c^48);c=getchar();}return s*w;}

int n,kk,tot;
vector <int> a[10];
queue <string> q;
map <string,bool> mp;
string s;

inline void bfs(string s){
  tot=1;
  q.push(s);
  mp[s]=true;//初始操作。
  while(!q.empty()){
    string now=q.front();
    q.pop();
     int lenn=now.size();
    rep(i,0,lenn-1){
      int lens=a[now[i]-'0'].size();
      rep(j,0,lens-1){
          string nxt=now;
          nxt[i]=(a[now[i]-'0'][j]+'0');//修改。
          if(!mp[nxt]){//没有出现过。
            mp[nxt]=true;
            q.push(nxt);//入队。
            tot++;
          }
      }
    }
  }
  pr("%lld\n",tot);
}

signed main(){
  n=read();kk=read();
  while(n){
    s+=to_string(n%10);
    n/=10;
  }
  int len=s.size();
  rep(i,0,len/2-1) swap(s[i],s[len-i-1]);//翻不翻转无所谓啦。
  rep(i,1,kk){
    int x=read(),y=read();
    if(x!=y) a[x].push_back(y);
  }
  bfs(s);
  return 0;
}