[R29D]平滑数 - 代码源竞赛平台

时空限制

1S/512M

题目描述

在数字的世界里，有一些数因其独特的结构而被称为“平滑数”。一个 $n$ 位非负整数 $X$ 被称为平滑数，当且仅当其任意两个相邻数位的数字之差的绝对值不大于 $1$。

例如，$12321$ 是一个平滑数，因为 $|1-2|=1, |2-3|=1, |3-2|=1, |2-1|=1$。而 $132$ 不是平滑数，因为 $|1-3|=2 > 1$。

给定 $m$ 个限制，每个限制形如 $(a_i, b_i)$，要求该 $n$ 位数的第 $a_i$ 位（从左数第 $1$ 位为最高位）必须是数字 $b_i$。

请找出满足所有限制条件且最小的 $n$ 位平滑数。

注意：若 $n > 1$，则 $n$ 位数的最高位不能为 $0$。

格式

输入格式

第一行包含两个整数 $n, m$，分别表示数字的长度和限制的数量。

接下来 $m$ 行，每行包含两个整数 $a_i, b_i$，表示一个限制条件，即第 $a_i$ 位的数字必须是 $b_i$。

输出格式

输出一行。如果存在满足条件的数，输出最小的一个。如果不存在，输出 -1。

样例

样例输入 #1

5 2
2 4
5 2

样例输出 #1

34322

样例输入 #2

5 2
2 1
5 5

样例输出 #2

-1

数据规模

对于 $20\%$ 的数据，$1 \leq n \leq 6$。

对于 $40\%$ 的数据，$1 \leq n \leq 2000$。

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq n$，$1 \leq a_i \leq n$，$0 \leq b_i \leq 9$，且给出的所有 $a_i$ 互不相同。