クラクフのヤギェウォ大学での勉強には、長所と短所がある。長所：ヤギェウォ大学。短所：クラクフ……あるいは、より正確には、路面電車の線路の改修に常に対処しなければならないことである。

当初、公共交通機関のネットワークはいくつかの路面電車の路線で構成されている。その後、ある路線が運休になり、また別の路線が運休になり、さらにまた……。ご存知の通り、クラクフの不変のルールは、以前に運休になった路線が運行を再開する前に、必ず別の路線を運休にすることである。現在、すべての路線が（まだ）運休になっているわけではないが、あなたは路面電車に乗っていて、大学への直通接続が消滅したことに腹を立てている。窓の外を見て、あなたは自問する。「私はこの街で本当に最も運の悪い乗客なのだろうか？ それとも、目的地にたどり着くために、私よりもさらに多くの乗り換えを必要としている誰かが、どこかにいるのだろうか？」

より正確に定義すると、停留所 $B$ が停留所 $A$ から $c$ 回の乗り換えで到達可能であるとは、路線 $l_0, \dots, l_c$ が存在し、$l_0$ が停留所 $A$ に停車し、$l_c$ が停留所 $B$ に停車し、かつ各 $0 \le i < c$ に対して、路線 $l_i$ と $l_{i+1}$ の両方に停車する停留所が存在することを指す。各時点において、あなたは、停留所 $A$ から $c$ 回の乗り換えで到達可能であり、かつ任意の $c' < c$ に対して停留所 $A$ から $c'$ 回の乗り換えでは到達不可能であるような停留所のペア $(A, B)$ が存在するような、$c$ の最大値を知りたい。

注記として、停留所のペア間を移動することが全く不可能な場合があるかもしれない。上記の定義に従い、そのようなペアは分析の対象から除外することにする。つまり、そのような停留所間を移動したい場合は、いずれにせよUberを利用するだろうと結論付ける。

入力

入力の最初の行には、テストケースの数 $z$ ($1 \le z \le 35$) が含まれる。続いて各テストケースの説明が続く。

各テストケースの最初の行には、停留所の数 $n$ と路面電車の路線の数 $k$ ($2 \le n, k \le 750$) が含まれる。停留所には $1$ から $n$ までの番号が、路線には $1$ から $k$ までの番号が付けられている。

続いて $k$ 行が続く。そのうちの $i$ 番目の行は、路線番号 $i$ の経路を記述する。各行は整数 $r_i$ ($2 \le r_i \le n$) で始まり、続いて $r_i$ 個の異なる整数 $a_{i,j}$ ($1 \le a_{i,j} \le n$) が続く。これらは $i$ 番目の路線が停車する停留所の識別子である。どの路面電車の路線も双方向に運行する。

次の行には、単一の整数 $s$ ($1 \le s \le k - 1$) が含まれる。

続いて $s$ 行が続く。これらは路面電車の路線が運休になる順序を記述する。これらの各行には、単一の整数 $s_i$ ($1 \le s_i \le k$) が含まれる。これは運休になる路面電車の路線の識別子である。どの路線も最大で一度だけ運休になる。

すべてのテストケースにおける $n$ と $k$ の値の合計は、それぞれ $1000$ を超えない。

出力

各テストケースについて、$s + 1$ 行を出力せよ。各行には単一の整数が含まれる。$i + 1$ 番目の行は、$i$ 番目の運休イベントが発生した後の（最初の行は運休前の回答を示す）必要な乗り換え回数の最大値を示すものとする。

入出力例

入力 1

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

出力 1

1
2
0
0

注記

当初は、例えば停留所 4 から停留所 5 へ（またはその逆）移動するために、1 回の乗り換えが必要である。このような移動は、路線 2 に乗り、次に路線 1 に乗ることで可能である。2 回以上の乗り換えを必要とする停留所のペアは存在しない。

路線 1 が削除された後、停留所 1 から停留所 3 へ（またはその逆）移動するために、2 回の乗り換えが必要となる。

路線 1 と 4 が削除されたとき、互いに到達可能な停留所のペアは (1, 4) と (2, 3) のみであり、どちらの場合も移動に乗り換えは必要ない。

路線 1、4、3 が削除されたとき、互いに到達可能な停留所のペアは (1, 4) のみである。これらの停留所間を移動するのに乗り換えは必要ない。