傳遞閉包，矩陣相乘。
#include <stdio.h>
#include <string.h>
#define N 105
struct Matrix
{
int mat[N][N];
};
void print(Matrix g, int n)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
printf("%3d", g.mat[i][j]);
}
printf("\n");
}
}
Matrix MatrixMul(Matrix t, Matrix g, int n)
{
Matrix ans;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
int sum = 0;
for(int k = 1; k <= n; k++)
{
sum |= t.mat[i][k] & g.mat[k][j];
}
ans.mat[i][j] = sum;
}
}
return ans;
}
Matrix MatrixPow(Matrix g, int n, int d)
{
Matrix t;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i == j) t.mat[i][j] = 1;
else t.mat[i][j] = 0;
}
}
// print(t, n);
while(d)
{
if(d & 1) t = MatrixMul(t, g, n);
g = MatrixMul(g, g, n);
d >>= 1;
}
return t;
}
int main()
{
//freopen("in", "r", stdin);
int n, m, s, e, d;
Matrix g;
while(scanf("%d %d", &n, &m), n + m)
{
memset(g.mat, 0, sizeof(g.mat));
for(int i = 0; i < m; i++)
{
scanf("%d %d", &s, &e);
g.mat[s][e] = g.mat[e][s] = 1;
}
scanf("%d %d %d", &s, &e, &d);
g = MatrixPow(g, n, d);
if(g.mat[s][e]) puts("Yes, Teobaldo can travel.");
else puts("No, Teobaldo can not travel.");
}
return 0;
}