/*
最短路, 終點(diǎn)集合到s的最遠(yuǎn)距離最短，求s. 即已知終點(diǎn)集g80qik8求一s使得Min{ max{ dis(s, di) } }
好題
思路： 多次單源最短路，選出最大值
在對(duì)每個(gè)x進(jìn)行分層搜索的過(guò)程中, 用max_d[y]記錄每個(gè)地區(qū)x到達(dá)地區(qū)y的最短距離中的最大值. 最后求得的Star Value就是max_d[]中的最小值.
由于題目的特殊性`邊權(quán)都為1`，所以可以借助這一性質(zhì)變換一下SPFA使其更快。
說(shuō)個(gè)題外話，在臨高時(shí)看到有個(gè)學(xué)弟拓?fù)渑判蛴玫?#8220;分層思想”，一直覺(jué)得很妙。就是拓?fù)浜笪覀兛梢缘玫絝loor[i]，如果floor[i] > floor[j]，即說(shuō)明j是i的前驅(qū)節(jié)點(diǎn)（層數(shù)越小越接近root）; 而floor[i] == floor[j]的話則i，j的相對(duì)順序無(wú)所謂，因?yàn)樗麄兌荚?#8220;同一層”。
這里因?yàn)檫厵?quán)都為1，所以SPFA可以用到上述的分層思想，層數(shù)越高，離source越遠(yuǎn)。代碼里面floors就表示層數(shù)，Q是滾動(dòng)隊(duì)列，就是一層一層地relax后繼節(jié)點(diǎn)。
注意！！千萬(wàn)不要以為max_d[]是最短路算法里面的dis[]，這里的max_d[i]是到點(diǎn)i到終點(diǎn)集合{di}的最大值！而常規(guī)最短路算法里的dis[]已經(jīng)被省略為“層數(shù)”了，不需要記錄，所以沒(méi)開(kāi)數(shù)組。
最重要的是學(xué)到一個(gè)tip！！以前我做多次最短路的時(shí)候總要每次都初始化visit[] -> false，但其實(shí)不用的，我們只要用一個(gè)變量when表示“這是第幾次做SPFA(或其他)“，然后每次入隊(duì)前都看”是否當(dāng)前visit[v] == when就可以直到改點(diǎn)是否已經(jīng)入過(guò)隊(duì)......
*/
#include <stdio.h>
#include <string.h>
#include <vector>
#include <deque>
using namespace std;
#define debug printf("!\n")
#define INF 999999999
#define MAXN 10000
int n;
int max_d[MAXN];
int visit[MAXN];
vector<int> v[MAXN];
void SPFA(int s, int when);
void init();
int main()
{
int cases, query, id, m, y, x;
scanf("%d", &cases);
while(cases--) {
scanf("%d%d", &n, &query);
init();
for(int i = 0; i < n; i++) {
scanf("%d%d", &id, &m);
while(m--) {
scanf("%d", &y);
v[id].push_back(y);
}
}
int when = 0;
while(query--) {
scanf("%d", &m);
while(m--) {
scanf("%d", &x);
SPFA(x, ++when);
}
}
int ans = INF, ans_id = -1;
for(int i = 1; i < MAXN; i++) if(!v[i].empty() && max_d[i] < ans) ans = max_d[i], ans_id = i;
printf("%d %d\n", ans, ans_id);
}
return 0;
}
void init()
{
for(int i = 0; i < MAXN; i++) v[i].clear();
memset(max_d, 0, sizeof(max_d));
memset(visit, 0, sizeof(visit));
}
void SPFA(int s, int when)
{
deque<int> Q[2];
int cur = 0;
Q[cur].push_back(s);
max_d[s] = max(max_d[s], 1);
visit[s] = when;
int floors = 1;
do {
floors++;
while(!Q[cur].empty()) {
int at = Q[cur].front();
Q[cur].pop_front();
for(int Size = v[at].size(), i = 0; i < Size; i++) {
int to = v[at][i];
if(visit[to] != when) { //是否已入隊(duì)
//max_d[to] = max(max_d[to], max_d[at]+1); 這句是不對(duì)的，因?yàn)檫@個(gè)分層跟拓?fù)渑判虻姆謱邮遣灰粯拥模負(fù)渑判蚴且谌攵葹?時(shí)才能加進(jìn)隊(duì)Q，所以可以這樣寫(xiě)，但是這里只要第一次遇見(jiàn)點(diǎn)to就必須得入隊(duì)，因?yàn)橐氖亲疃搪窂?/span>
max_d[to] = max(max_d[to], floors); //不把這句放在if外面，因?yàn)檫@里的max_d[to]是距離s的最短路徑，最短路徑也就是最小層數(shù)，最小層數(shù)在to第一次入隊(duì)的時(shí)候已經(jīng)得到了
visit[to] = when;
Q[1-cur].push_back(to);
}
}
}
cur = 1 - cur;
} while(!Q[cur].empty());
}