2013年9月18日 星期三

1148 - The mysterious X network

École 理工學院已經存在深根柢固的同儕網路。

當同學遇到任何困難時,他可以藉由這個網路尋求協助,也就是說,他想要在網路上找到另一個人尋求協助,他必須由中間人代為轉達。

特別注意:同儕關係都是對稱的,而且必然可以找到所有人。

寫一個程式計算最少的中間人個數。

Input


輸入第一行有一個整數,表示有多少測資組。

對於每組測資,第一行會有一個整數 N (1 <= N <= 105),同儕編號為 0 到 N-1。

接下來會有 N 行,每行前 2 個整數 c, nc ( <= 100) 表示同儕編號,以及關係個數。

接下來會有 nc 個整數緊接在後,表示 c 的同儕。

最後一行會有兩個整數 c1c2 ,表示 c1c2 求助。

Output


對於每組測資,分別輸出 
c1, c2, 和最少中間人個數。

Sample Input 


1

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

Sample Output 


1 2 1