P7658 [BalticOI 2000] MUTEXES (Day 2)

现代编程语言允许编写由多个执行线程组成的程序。这就好像有几个程序在同一个地址空间并行运行，访问相同的变量。通常，线程需要彼此同步。例如，一个线程可能需要等待另一个线程完成某些计算并将结果存储到某个变量中。 最简单的线程同步工具是互斥锁。互斥锁是一种特殊的对象，可以处于锁定或解锁状态。锁定的互斥锁始终由一个线程拥有。线程可以对互斥锁应用两种操作：LOCK 和 UNLOCK。 当线程对当前未锁定的互斥锁应用 LOCK 时，该互斥锁将被锁定并且该线程获得该互斥锁的所有权。如果一个线程尝试将 LOCK 应用于已被其他线程锁定的互斥锁，则该线程将被阻塞，直到该互斥锁被解锁。 当线程对其拥有的互斥锁应用 UNLOCK 时，该互斥锁将变为未锁定状态。如果有其他线程等待锁定互斥锁，则其中一个线程被授予互斥锁的所有权。如果有多个线程在等待，则任意选择一个。 多线程程序中的常见问题之一是死锁。当两个或多个线程正在等待彼此释放互斥锁并且它们都不能继续时，就会发生死锁。当一个线程正在等待被另一个线程锁定的互斥锁时，也会发生死锁，该线程已终止而没有释放互斥锁。 现为您提供一些线程的描述，您的任务是确定是否会发生死锁。 每个线程都是以下形式的指令序列： ``LOCK `` ``UNLOCK `` 您可以假设以下有关命令： - 互斥锁的名称是大写字母 A$\cdots$Z； - 没有线程试图锁定它已经拥有的互斥锁； - 没有线程试图解锁不属于它的互斥锁。

第一行包含一个整数为线程数 $M$，后跟描述每个线程的 $M$ 个块。描述线程 $i$ 的块的第一行包含一个整数为该线程中的指令数 $N_i$，然后是 $N$ 行指令。指令不包含多余的空格。

第一行必须包含一个整数：$D$。如果可能出现死锁，$D$ 必须为 $1$，否则为 $0$。 如果可能出现死锁，则第二行必须描述发生死锁的程序状态。如果存在多个死锁状态，则输出其中任何一个。在这种情况下，我们寻找的是完全死锁，即没有一个线程可以继续执行——线程必须被互斥锁终止或阻塞。如果不可能出现死锁，则该行必须为空。 程序状态通过按照线程在输入中出现的顺序为每个线程指定当前指令的从零开始的索引来描述。对于终止的线程，输出 $-1$ 作为索引。 索引必须在一行上并用空格分隔。

#### 数据规模与约定 对于 $100 \%$ 的数据，$1 \le M \le 5$，$1 \le N_i \le 10$。 #### 分值说明 本题分值按 BOI 原题设置，**满分** $60$ 。 #### 题目说明 来源于 [Baltic Olympiad in Informatics 2000](http://ingforum.haninge.kth.se/BOI00/boi00.html) 的 [Day 2:Mutexes](http://ingforum.haninge.kth.se/BOI00/BOI007.html#anchor84989)。 由 @[求学的企鹅](/user/271784) 翻译整理。