Description

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.

Input Format

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 Format

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

234 2
2 5
3 6

4

Hint

Constraints: For $100\%$ of the testdata, $n < 10^{30}$, $k \le 15$.

Problem Source: NOIP 2002 Junior, Problem 3.

Translated by ChatGPT 5