#NOIPJ2002D. 产生数

产生数

题目描述

给出一个整数 nnn2000n \le 2000)和 kk 个变换规则(k15k \le 15)。规则:

11 个数字可以变换成另 11 个数字;

② 规则中,右边的数字不能为零。

例如:n=234n=234k=2k=2 规则为

252 → 5

363 → 6

上面的整数 234234 经过变换后可能产生出的整数为(包括原数)23423453453426426456456444 种不同的产生数。

求经过任意次的变换(00 次或多次),能产生出多少个不同的整数。仅要求输出不同整数个数。

输入格式

第一行两个整数 nnkk

接下来 kk 行,每行两个整数 xix_iyiy_i

输出格式

输出能生成的数字个数。

234
2
2 5
3 6
4