P1037 [NOIP 2002 Junior] Generated Numbers

Given an integer $n$ and $k$ transformation rules. Rules: - A single digit can be transformed into another single digit. - The right-hand side of a rule cannot be zero. For example: $n = 234, k = 2$. There are two rules: - $2\longrightarrow 5$. - $3\longrightarrow 6$. After applying transformations, the integer $234$ can produce the following integers (including the original number): - $234$. - $534$. - $264$. - $564$. There are $4$ distinct generated numbers. Now, given an integer $n$ and $k$ rules, determine how many different integers can be produced by applying any number of transformations (zero or more). Only output the count.

The first line contains two integers $n, k$, as described. The next $k$ lines each contain two integers $x_i, y_i$, representing each rule.

Output a single line containing the number of distinct integers that can be generated.

Constraints: For $100\%$ of the testdata, $n < 10^{30}$, $k \le 15$. Problem Source: NOIP 2002 Junior, Problem 3. Translated by ChatGPT 5