← 返回题目列表

Codeforces · 325/C

C. 怪物和钻石

中文机器翻译题面 查看原题

Piegirl 发现了一个怪物和一本关于怪物和馅饼的书。当她看书时,她发现有n种怪物,每种怪物的ID在1到n之间。如果你给怪物喂馅饼,怪物会分裂成一定数量的怪物(可能为零),以及至少一颗彩色钻石。怪物可能能够以多种方式分裂。

一开始,Piegirl只有一个怪物。她首先给怪物喂了一块馅饼。她继续给怪物喂馅饼,直到不再有怪物为止。然后她收集了所有创造的钻石。

您将获得一份分裂规则列表,描述各种怪物的分裂方式。每个怪物至少可以以一种方式分裂,如果一个怪物可以以多种方式分裂,那么每次分裂时Piegirl都可以选择它的分裂方式。

对于每个怪物,确定 Piegirl 可能收集的最小和最大钻石数量(如果她最初只有该怪物的单个实例)。 Piegirl 的馅饼无限量供应。

输入

第一行包含两个整数:m和n(1≤m,n≤105),可能的分裂数量和不同怪物类型的数量。接下来的 m 行每一行都包含一条分割规则。每个分裂规则以一个整数(怪物ID)mi(1≤mi≤n)开头,以及一个正整数li,表示当前怪物可以分裂成的怪物和钻石的数量。后面跟着li个整数,正整数代表怪物ID,-1代表钻石。

每个怪物至少有一个分割规则。每个分割规则至少有一颗钻石。所有分割规则的 li 之和最多为 105。

输出

对于每个怪物,按照其 ID 的顺序,打印一行包含两个整数的行:从该怪物开始可能收集的最小和最大钻石数。如果 Piegirl 不可能最终处于没有怪物的状态,则为最小值和最大值都打印 -1。如果她可以收集任意数量的钻石,则打印 -2 作为最大的钻石数量。

如果输出中的任何数字超过 314000000(但有限),则打印 314000000 而不是该数字。

示例

输入 #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