P13640 [NWRRC 2021] Multithreaded Program

Maurice 正在他的老旧机器上调试一个多线程程序。该程序有若干线程操作一组共享变量。每个线程按照预定的“程序顺序”执行自己的赋值序列。每次赋值会将某个变量设置为一个整数值。 当程序运行时，不同线程的赋值可以以任意顺序执行。唯一的保证是，每个线程内部的赋值必须按照程序顺序依次执行。 例如，假设程序有三个线程，它们的赋值序列长度分别为 $2$、$2$ 和 $1$。那么一种合法的程序执行顺序如下： - 线程 $1$ 执行其序列中的第一个赋值； - 线程 $2$ 执行其序列中的第一个赋值； - 线程 $2$ 执行其序列中的第二个赋值； - 线程 $1$ 执行其序列中的第二个赋值； - 线程 $3$ 执行其唯一的赋值。 这种执行顺序可以描述为 $1, 2, 2, 1, 3$，其中数字表示每一步执行赋值的线程编号。注意，还存在许多其他合法的执行顺序。 Maurice 怀疑他的机器有故障，可能会出现错误的行为。他已经运行了程序，并记录了所有变量在结束时的值。 请你找出一种执行顺序，使得所有赋值都被执行，并且最终所有变量的值与记录一致；或者报告机器确实有故障，不存在这样的执行顺序。

第一行包含一个整数 $t$，表示线程数（$1 \leq t \leq 100$）。线程编号为 $1$ 到 $t$。接下来的 $t$ 段描述每个线程的赋值序列，每段一行。 第 $i$ 段的第一行包含一个整数 $l_i$，表示第 $i$ 个线程的赋值序列长度（$1 \leq l_i \leq 100$）。接下来的 $l_i$ 行，每行包含一个赋值，格式为 $\texttt{=}$. 这些赋值按照程序顺序给出。变量名由不超过 $10$ 个小写英文字母组成，赋值为不超过 $10^9$ 的正整数。 剩下的第一行包含一个整数 $k$，表示变量的数量（$1 \le k \le 10\,000$）。接下来的 $k$ 行，每行包含一个变量名和其记录的值，均为不超过 $10^9$ 的正整数。每个在程序中出现过的变量恰好出现一次，且每个列出的变量至少在某个赋值中被使用过。

如果存在一种执行顺序能得到记录的变量值，输出 $\texttt{Yes}$；否则输出 $\texttt{No}$。 如果存在可行的执行顺序，输出一行 $s = l_1 + l_2 + \dotsb + l_t$ 个整数 $c_1, c_2, \ldots, c_s$，描述一种合法的执行顺序（$1 \le c_i \le t$）。这表示第 $i$ 步执行赋值的线程编号为 $c_i$。每个线程的赋值必须按照程序顺序依次执行。第 $i$ 个线程在序列中恰好出现 $l_i$ 次。执行完第 $s$ 步后，每个变量的值必须与记录值一致。

由 ChatGPT 4.1 翻译