325_C. 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.

Input

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) mi (1 ≤ mi ≤ n), and a positive integer li indicating the number of monsters and diamonds the current monster can split into. This is followed by li 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 li across all split rules will be at most 105.

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
```python
import sys, heapq

_BLANCO, _GRIS, _NEGRO = 0, 1, 2
_OO = int(1e18)


class Regla:
    def __init__(self, id, diamantes, deMonstruo, monstruos):
        self.id = id
        self.diamantes = diamantes
        self.deMonstruo = deMonstruo
        self.monstruos = monstruos

    def clonar(self):
        return Regla(self.id, self.diamantes, self.deMonstruo, self.monstruos[:])


def esUnaMalaRegla(r, d):
    for m in r.monstruos:
        if d[m] == _OO:
            return True

    return False


def dfsVisit(u, color, reglas, diamMax, d):
    color[u] = _GRIS

    for r in reglas[u]:
        if esUnaMalaRegla(r, d):
            continue

        sumaMax = r.diamantes

        for v in r.monstruos:
            if color[v] == _BLANCO:
                dfsVisit(v, color, reglas, diamMax, d)

                if diamMax[v] > 0:
                    sumaMax += diamMax[v]

            elif color[v] == _GRIS:
                diamMax[v] = -2

            elif color[v] == _NEGRO:
                sumaMax += diamMax[v]

            if diamMax[v] == -2:
                diamMax[u] = -2
                color[u] = _NEGRO
                return

        diamMax[u] = max(diamMax[u], sumaMax)

    color[u] = _NEGRO


def dfs(reglas, d):
    n = len(reglas)
    color, diamMax = [], []

    for i in range(n):
        color.append(_BLANCO)
        diamMax.append(0)

    for u in range(n):
        if color[u] == _BLANCO:
            dfsVisit(u, color, reglas, diamMax, d)

    return diamMax


def dijkstra(reglas, s, m, perteneceA):
    n = len(reglas)
    d = []
    Q, visto = [], []
    k, sumaMin = [0] * m, []
            
    for u in range(n):
        d.append(_OO)
        visto.append(False)

        for r in reglas[u]:
            sumaMin.append(0)
            k[r.id] = len(r.monstruos)

    d[s] = 0
    Q.append((0, s))
    heapq.heapify(Q)

    while len(Q) != 0:
        u = heapq.heappop(Q)[1]

        if visto[u]:
            continue

        visto[u] = True

        for p in perteneceA[u]:
            r = reglas[p[0]][p[1]]
            ocurrencias = p[2]

            k[r.id] -= ocurrencias
            sumaMin[r.id] += d[u] * ocurrencias

            if k[r.id] == 0 and d[r.deMonstruo] > sumaMin[r.id] + r.diamantes:
                d[r.deMonstruo] = sumaMin[r.id] + r.diamantes;
                heapq.heappush(Q, (d[r.deMonstruo], r.deMonstruo))

    return d


def anyadirVerticeFicticio(reglas, perteneceA):
    n = len(reglas)
    nuevasReglas = []

    perteneceA.append([])  # pertenencia del vertice ficticio

    for u in range(n):
        nuevasReglas.append([])

        for r in reglas[u]:
            nuevasReglas[u].append(r.clonar())

            if len(r.monstruos) == 0:
                nuevasReglas[u][-1].monstruos.append(n)  # anyadiendo vertice ficticio
                perteneceA[n].append((u, len(nuevasReglas[u]) - 1, 1))

    nuevasReglas.append([])  # reglas del vertice ficticio

    return nuevasReglas


def resolver(reglas, m, perteneceA):
    n = len(reglas)

    reglasConVertFicticio = anyadirVerticeFicticio(reglas, perteneceA)
    d = dijkstra(reglasConVertFicticio, n, m, perteneceA)
    diamMax = dfs(reglas, d)

    UPPER = 314000000

    for u in range(n):
        if d[u] < _OO:
            sys.stdout.write("%d %d" % (min(d[u], UPPER), min(diamMax[u], UPPER)))

        else:
            sys.stdout.write("-1 -1")

        sys.stdout.write("\n")


def leer_enteros():
    return [int(cad) for cad in sys.stdin.readline().split()]


if __name__ == "__main__":
    m, n = leer_enteros()

    ocurr, perteneceA, reglas = [], [], []

    for i in range(n):
        ocurr.append(0)
        perteneceA.append([])
        reglas.append([])

    for i in range(m):
        enteros = leer_enteros()
        mi = enteros[0] - 1

        r = Regla(i, 0, mi, [])

        for x in enteros[2:]:
            x -= 1

            if x >= 0:
                ocurr[x] += 1
                r.monstruos.append(x)

            else:
                r.diamantes += 1

        for mons in r.monstruos:
            if ocurr[mons] != 0:
                perteneceA[mons].append((mi, len(reglas[mi]), ocurr[mons]))

            ocurr[mons] = 0

        reglas[mi].append(r)

    resolver(reglas, m, perteneceA)
```