human
You are given a book with n chapters.

Each chapter has a specified list of other chapters that need to be understood in order to understand this chapter. To understand a chapter, you must read it after you understand every chapter on its required list.

Currently you don't understand any of the chapters. You are going to read the book from the beginning till the end repeatedly until you understand the whole book. Note that if you read a chapter at a moment when you don't understand some of the required chapters, you don't understand this chapter.

Determine how many times you will read the book to understand every chapter, or determine that you will never understand every chapter no matter how many times you read the book.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 2⋅10^4).

The first line of each test case contains a single integer n (1 ≤ n ≤ 2⋅10^5) — number of chapters.

Then n lines follow. The i-th line begins with an integer k_i (0 ≤ k_i ≤ n-1) — number of chapters required to understand the i-th chapter. Then k_i integers a_{i,1}, a_{i,2}, ..., a_{i, k_i} (1 ≤ a_{i, j} ≤ n, a_{i, j} ≠ i, a_{i, j} ≠ a_{i, l} for j ≠ l) follow — the chapters required to understand the i-th chapter.

It is guaranteed that the sum of n and sum of k_i over all testcases do not exceed 2⋅10^5.

Output

For each test case, if the entire book can be understood, print how many times you will read it, otherwise print -1.

Example

Input

5
4
1 2
0
2 1 4
1 2
5
1 5
1 1
1 2
1 3
1 4
5
0
0
2 1 2
1 2
2 2 1
4
2 2 3
0
0
2 3 2
5
1 2
1 3
1 4
1 5
0

Output

2
-1
1
2
5

Note

In the first example, we will understand chapters \{2, 4\} in the first reading and chapters \{1, 3\} in the second reading of the book.

In the second example, every chapter requires the understanding of some other chapter, so it is impossible to understand the book.

In the third example, every chapter requires only chapters that appear earlier in the book, so we can understand everything in one...
Solve the task in PYTHON3.
 ... What is a Python program to determine how many times you will read the book to understand every chapter, or determine that you will never understand every chapter no matter how many times you read the book?
assistant
#Here is Python program to determine how many times you will read the book to understand every chapter, or determine that you will never understand every chapter no matter how many times you read the book.

import sys
from sys import stdout

input = lambda: sys.stdin.readline().strip()
P = lambda: list(map(int, input().split()))
from math import factorial as f, gcd, ceil
from collections import deque, defaultdict as dd, Counter as C
from heapq import heapify, heappop, heappush, heappushpop, heapreplace, merge
from random import randint, choice, sample
from operator import itemgetter as ig, attrgetter as ag, methodcaller as mc
import time
mod = 10**9+7
a = ord('a')

# Fenwick Tree
class FT:
    def __init__(self, N):
        self.ft = [0] * (N+1)
        self.N = N

    def ls(self, x):
        return x & -x

    def fenwick_update(self, p, v):
        while p <= self.N:
            self.ft[p] += v
            p += self.ls(p)

    def fenwick_query(self, p):
        s = 0
        while p:
            s += self.ft[p]
            p -= self.ls(p)
        # print(p, s)
        return s

start = time.time()
def fast_exp(x, exp):
    ans = 1
    base = x
    while exp:
        if exp & 1:
            ans *= base
        base *= base
        base %= mod
        ans %= mod
        exp >>= 1
    return ans

def countBits(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

def submasks(n):
    #this is cool
    #https://cp-algorithms.com/algebra/all-submasks.html
    org = n
    while n:
        yield n
        n = (n-1) & org

# Inverse things: very magic
# https://www.youtube.com/watch?v=-OPohCQqi_E&ab_channel=Errichto
# MOD MUST BE PRIME

def inv_mod(a):
    # Euler's theorem (?)
    return fast_exp(a, mod-2)

def mod_div(a, b):
    return a * inv_mod(b) % mod

N = 200000
fac = [1] * N
invfac = [1] * N

def prep_fac(n):
    global fac, invfac
    fac.append(1)
    invfac.append(1)
    for i in range(1, n+1):
        fac[i] =((fac[i-1] * i) % mod)
        invfac[i] = ((invfac[i-1] * inv_mod(i)) % mod)

def ncr(n, r):
    return (fac[n] * invfac[r] * invfac[n-r]) % mod

def solve():
    n = int(input())
    req = [P() for _ in range(n)]

    # adj stores things that need this chapter
 ...