← 返回题目列表

Codeforces · 1679/F

F. 形式主义的形式主义

中文机器翻译题面 查看原题

尤拉是一位数学家,他对世界的认知是如此绝对,就好像他已经解决了一百万亿亿年的形式问题一样。这个问题仅此而已!

考虑区间 $$$[0, 10^{n})$$$ 中的所有非负整数。为了方便起见,我们用前导零对所有数字进行补足,使得给定区间中的每个数字恰好由 $$$n$$$ 十进制数字组成。

给你一组$$$(u_i, v_i)$$$,其中$$$u_i$$$ 和$$$v_i$$$ 是从$$$0$$$ 到$$$9$$$ 的不同十进制数字。

考虑一个由 $$$n$$$ 数字组成的数字 $$$x$$$。我们将从左到右枚举所有数字,并将它们表示为 $$$d_1, d_2, \ldots, d_n$$$。在一次操作中,当且仅当集合中存在一对 $$$(u_j, v_j)$$$ 且至少满足以下条件之一时,您可以交换数字 $$$d_i$$$ 和 $$$d_{i + 1}$$$:

1. $$$d_i = u_j$$$ 且 $$$d_{i + 1} = v_j$$$,
2. $$$d_i = v_j$$$ 且 $$$d_{i + 1} = u_j$$$。

我们将由 $$$n$$$ 数字组成的数字称为 $$$x$$$ 和 $$$y$$$,如果可以使用上述一些操作将数字 $$$x$$$ 转换为数字 $$$y$$$,则等效。特别是,每个数字都被认为与其自身相等。

给你一个整数 $$$n$$$ 和一组 $$$m$$$ 数字对 $$$(u_i, v_i)$$$。您必须找到最大整数 $$$k$$$,使得存在一组整数 $$$x_1, x_2, \ldots, x_k$$$ ($$$0 \le x_i < 10^{n}$$$),使得对于每个 $$$1 \le i < j \le k$$$,数字 $$$x_i$$$ 不等于数字 $$$x_j$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50\,000$$$) — 所考虑数字的位数。

第二行包含一个整数 $$$m$$$ ($$$0 \le m \le 45$$$) — 集合中数字对的数量。

以下 $$$m$$$ 行均包含两个数字 $$$u_i$$$ 和 $$$v_i$$$,以空格分隔 ($$$0 \le u_i < v_i \le 9$$$)。

保证所有描述的对都是成对不同的。

输出

打印一个整数 - 最大值 $$$k$$$,使得存在一组整数 $$$x_1, x_2, \ldots, x_k$$$ ($$$0 \le x_i < 10^{n}$$$),使得对于每个 $$$1 \le i < j \le k$$$,数字 $$$x_i$$$ 不等于数字$$$x_j$$$。

由于答案可能足够大,因此打印数字 $$$k$$$ 模 $$$998\,244\,353$$$。

示例

输入 #1

1
0

输出 #1

10

输入 #2

2
1
0 1

输出 #2

99

输入 #3

2
9
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

输出 #3

91

注意

在第一个示例中,我们可以构造一个包含从 $$$0$$$ 到 $$$9$$$ 的所有整数的集合。很容易看出集合中没有两个相等的数字。

在第二个示例中,存在一对唯一的等效数字:$$$01$$$ 和 $$$10$$$。我们可以构造一个包含从 $$$0$$$ 到 $$$99$$$ 的所有整数的集合,尽管数字为 $$$1$$$。