CF325C.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.

Piegirl 发现了一只怪物和一本关于怪物与派的书。当她阅读这本书时，发现一共有 $n$ 种怪物，每种怪物的编号为 $1$ 到 $n$。若给一只怪物喂一个派，该怪物便会分裂成若干只怪物（可能为零只），以及至少一颗彩色钻石。同一种怪物可能有多种不同的分裂方式。

初始时，Piegirl 恰好拥有一只怪物。她首先给这只怪物喂一个派。之后她持续给怪物喂派，直到不再剩下任何怪物为止。最后，她收集所有生成的钻石。

你将获得一份分裂规则列表，描述各类怪物可能的分裂方式。每种怪物至少有一种分裂方式；若某种怪物有多种分裂方式，则每次该怪物分裂时，Piegirl 均可自主选择采用哪一种方式。

对于每种怪物，请确定：若 Piegirl 最初仅拥有该种怪物的一只个体，在她拥有无限量派的前提下，她最终所能收集到的钻石数量的最小值与最大值分别是多少。

The first line contains two integers: m and n (1 ≤ m, n ≤ 105), 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 105.

第一行包含两个整数：$m$ 和 $n$（$1 \le m, n \le 10^5$），分别表示可能的分裂规则数量和不同怪物类型的数量。接下来的 $m$ 行中，每行描述一条分裂规则。每条分裂规则以一个整数（怪物编号）$m_i$（$1 \le m_i \le n$）和一个正整数 $l_i$ 开头，其中 $l_i$ 表示当前怪物可分裂产生的怪物与钻石的总数。随后是 $l_i$ 个整数：正整数表示怪物编号，$-1$ 表示一颗钻石。

每个怪物至少拥有一条分裂规则；每条分裂规则至少包含一颗钻石；所有分裂规则中 $l_i$ 的总和不超过 $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.

对于每个怪物，按照其 ID 的顺序，输出一行包含两个整数：从该怪物开始可能收集到的钻石数量的最小值和最大值。如果 Piegirl 不可能最终到达一个没有怪物的状态，则两个值均输出 -1；如果她可以收集任意多的钻石，则最大值输出 -2。

若输出中的任一数值超过 314000000（但为有限值），则用 314000000 代替该数值。