C++ :

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAXN 10001
#define MAXM 16
using namespace std;
int n,k;
int exist[MAXN];
int que[MAXN];
int a[MAXM],b[MAXM];
int main()
{
	scanf("%d",&n);
	scanf("%d",&k);
	for (int i=0;i<k;++i)
		scanf("%d%d",&a[i],&b[i]);
	exist[n]=1;
	int head=1;
	que[1]=n;	
	for (int tail=0;head>=tail;)
	{
		int x=que[++tail];
		int y=x,mod=1;
		while (x>0)
		{
			int tmp=x%10;
			x/=10;
			for (int i=0;i<k;i=i+1)
				if (a[i]==tmp)
				{
					int p=y+(b[i]-tmp)*mod;
					if (exist[p]==0)
					{
						exist[p]=1;
						que[++head]=p;
					}
				}
			mod*=10;
		}
	}
	cout<<head<<endl;
	return 0;
}