题目描述

给出一个整数n和k个变换规则，变换规则：

1. 一位数可变换成另一个一位数
2. 规则中，右部不能为零

例如：n=234。有规则（k=2）：

2－>5

3－>6

根据这两条变换规则，整数234经过变换后可能产生出的整数为（包括原数）234，534，264，564，共 4 种不同的产生数。

现在给出一个整数n和k个规则。求出经过任意次的变换（0次或多次），能产生出多少个不同整数。

输入格式

第一行两个整数n，k(n≤2000, k≤15)；

接下来k行，每行两个整数xi​，yi​，表示一条变换规则，xi​可以变换成yi​。

输出格式

输出能生成的数字个数。

输入/输出样例

234 2
2 5
3 6

4

234 2
2 5
2 8

3

说明/提示

时间1000ms，内存256MiB