One of the reasons for which École polytechnique (nicknamed ``X" for reasons to be explained during the debriefing talk) is so deeply rooted in French society is its famous network of camarades - former students of the same school. When one camarade wants something (money, job, etc.), he can ask this network for help and support. In practice, this means that when he/she wants to reach some other camarade, not always of the same year, then surely he can find intermediate camarades to get to her/him. Note that the ``camarade" relationship is symmetric. Due to the magic of the X network, there is always a means to reach anybody.

The program you have to write is supposed to help to minimize the number of these intermediate camarades.

Input 

The huge file of all living camarades is simplified so as to obey the following format. The first line in the file is the number of camarades, say N , an integer 1N10⁵ . Camarades are labeled from 0 to N - 1 . Follow N lines. Each line starts with the camarade label c , followed by the number of other camarades he/she knows, say n_c , followed by the labels of those n_c camarades. All these integers are separated by a single blank. It is assumed that n_c is always less than 100. The last line in the file is the label of the camarade seeking help (say c₁ ) followed by the label of the camarade he wants help from, say c₂ ( c₂ c₁ ).

Output 

Your program should output three integers separated by a blank: c₁ , c₂ and the minimal number of intermediate camarades to reach c₂ .

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

題目解法：

事實上只是單純地找到最短路。權重都是 1，直接 BFS。

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
vector<int> g[100005];
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int testcase;
    int n, m, x, y;
    int i, j, k, st, ed;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            g[i].clear();
        for(i = 0; i < n; i++) {
            //scanf("%d %d", &x, &m);
            ReadInt(&x);
            ReadInt(&m);
            while(m--) {
                //scanf("%d", &y);
                ReadInt(&y);
                g[x].push_back(y);
            }
        }
        scanf("%d %d", &st, &ed);
        queue<int> Q;
        int dist[100005] = {};
        Q.push(st);
        dist[st] = 1;
        while(!Q.empty()) {
            x = Q.front(), Q.pop();
            for(i = 0; i < g[x].size(); i++) {
                if(dist[g[x][i]] == 0) {
                    dist[g[x][i]] = dist[x]+1;
                    Q.push(g[x][i]);
                }
            }
            if(dist[ed])    break;
        }
        printf("%d %d %d\n", st, ed, dist[ed]-2);
        if(testcase)
            puts("");
    }
    return 0;
}