Monsters and Diamonds

题目描述

Piegirl has found a monster and a book about monsters and pies. When she is reading the book, she found out that there are $ n $ types of monsters, each with an ID between $ 1 $ and $ n $ . If you feed a pie to a monster, the monster will split into some number of monsters (possibly zero), and at least one colorful diamond. Monsters may be able to split in multiple ways. At the begining Piegirl has exactly one monster. She begins by feeding the monster a pie. She continues feeding pies to monsters until no more monsters are left. Then she collects all the diamonds that were created. You will be given a list of split rules describing the way in which the various monsters can split. Every monster can split in at least one way, and if a monster can split in multiple ways then each time when it splits Piegirl can choose the way it splits. For each monster, determine the smallest and the largest number of diamonds Piegirl can possibly collect, if initially she has a single instance of that monster. Piegirl has an unlimited supply of pies.

输入输出格式

输入格式

The first line contains two integers: $ m $ and $ n $ ( $ 1<=m,n<=10^{5} $ ), the number of possible splits and the number of different monster types. Each of the following $ m $ lines contains a split rule. Each split rule starts with an integer (a monster ID) $ m_{i} $ ( $ 1<=m_{i}<=n $ ), and a positive integer $ l_{i} $ indicating the number of monsters and diamonds the current monster can split into. This is followed by $ l_{i} $ integers, with positive integers representing a monster ID and -1 representing a diamond. Each monster will have at least one split rule. Each split rule will have at least one diamond. The sum of $ l_{i} $ across all split rules will be at most $ 10^{5} $ .

输出格式

For each monster, in order of their IDs, print a line with two integers: the smallest and the largest number of diamonds that can possibly be collected by starting with that monster. If Piegirl cannot possibly end up in a state without monsters, print -1 for both smallest and the largest value. If she can collect an arbitrarily large number of diamonds, print -2 as the largest number of diamonds. If any number in output exceeds $ 314000000 $ (but is finite), print $ 314000000 $ instead of that number.

输入输出样例

输入样例 #1

6 4
1 3 -1 1 -1
1 2 -1 -1
2 3 -1 3 -1
2 3 -1 -1 -1
3 2 -1 -1
4 2 4 -1

输出样例 #1

2 -2
3 4
2 2
-1 -1

输入样例 #2

3 2
1 2 1 -1
2 2 -1 -1
2 3 2 1 -1

输出样例 #2

-1 -1
2 2

题意翻译

### 题意 有 $n$ 种普通材料和 $m$ 种变换规则。普通材料编号从 $1$ 到 $n$，此外还有一种编号为 $-1$ 的特殊材料。 每种变换规则均形如，消耗一份**普通材料** $x_i$，获得材料 $p_{i,1}\dots p_{i,k_i}$ 各一份。 保证对于编号 $1\dots n$ 的每种材料至少有一个变换规则消耗该材料，保证每种变换规则至少产生一份特殊材料。 对于每种普通材料，你需要求出，若初始时恰有一份该材料，一直进行变换直至无法变换时，最少和最多各可获得多少特殊材料。 输出规则如下： 1. 若无论如何，变换均无法停止，该行输出 `-1 -1`。 2. 若你可以停止变换，也可以获得无限多的特殊材料，则该行最大值的位置输出 `-2`。 3. 若不满足以上两点，则你输出的答案对 $314000000$ 取 $\min$。 ### 读入 第一行两个整数 $m,n$，注意先 $m$ 后 $n$。 接下来 $m$ 行，每行描述一个变换规则。 首先两个正整数 $x_i,k_i$，表示消耗的材料和转化后物品数。接下来 $k_i$ 个数 $p_{i,1}\dots p_{i,k_i}$。 $n,m,\sum k_i\le 10^5$。