P14801 [CCPC 2024 哈尔滨站] 造计算机

你想要造一台计算机来实现一个功能：给出一个整数 $x$，判断 $x$ 是否在 $[L, R]$ 区间内。为此，你在电路中设计了一个边权为 $0$ 和 $1$ 的有向无环图，包含一个入度为 $0$ 的起点和一个出度为 $0$ 的终点。从起点出发沿着某一条路径走到终点，将经过的边权连成一个串，就可以得到 $[L, R]$ 范围内的一个整数的不含前导零的二进制表示，并且 $[L, R]$ 范围内的任意一个整数都能从这张图中找到唯一一条对应路径。这样一来，你只需要判断一个数的二进制表示是否能够通过这个有向无环图表达出来，就可以判断它是否在 $[L, R]$ 区间内。 显然，你可以将每个整数的对应路径分开成一条条链的形式，可你发现给出的范围很大时，这种有向无环图所需的节点太多了，你造的只有 256MiB 内存的计算机根本存不下。因此，你需要压缩这张有向无环图，即不同的路径之间可能会有共用的节点，使得这张图的点数和边数减少到一定范围内。形式化地说，你需要构造一个点数不超过 $100$，每个节点出度不超过 $200$ 的有向无环图，边权为 $0$ 和 $1$，有且仅有一个入度为 $0$ 的起点和一个出度为 $0$ 的终点。$[L, R]$ 中的每一个整数，都能与这张有向无环图中的一条起点到终点的路径 $\textbf{一一对应}$。具体地说，对于$[L, R]$ 中的任意一个整数，在图中有且仅有一条起点到终点的路径与之对应，且图中不存在一条起点到终点的路径能够对应 $[L, R]$ 范围之外的某一个整数。注意，图中的任意一条起点到终点的路径得到的二进制串均不能出现前导零。两点之间可以存在边权不同的两条边。

一行两个正整数 $L, R$ ($1 \le L \le R \le 10^6$)。

第一行输出节点数 $n$ ($1 \le n \le 100$)。 对于接下来 $n$ 行，第 $i$ 行先输出一个整数 $k$ ($0 \le k \le 200$)，表示节点 $i$ 的出边条数，接下来输出 $2 \cdot k$ 个正整数 $a_{i,k}, v_{i,k}$ ($1 \le a_{i,k} \le n$, $a_{i,k} \neq i$, $v_{i,k} \in \{0, 1\}$)，表示点 $i$ 有一条连向 $a_{i,k}$ 的边权为 $v_{i,k}$ 的有向边。你需要保证输出的是一张满足题目要求的有向无环图。