Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Monsters and Diamonds

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPiegirl 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.

Input

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

Output

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.

Examples

Input

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

Output

2 -2

3 4

2 2

-1 -1

Input

3 2

1 2 1 -1

2 2 -1 -1

2 3 2 1 -1

Output

-1 -1

2 2

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/28/2017 11:29:28 (c2).

Desktop version, switch to mobile version.
User lists

Name |
---|