#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <limits>
#include <time.h>
using namespace std;
#define mycom
#ifdef mycom
#include <fstream>
ifstream fin("input");
#else
#define fin cin
#endif
struct Node
{
string vertex;
Node* adj;
bool operator==(const Node& n) const
{
return (vertex == n.vertex);
}
bool operator<(const Node& n) const
{
return vertex < n.vertex;
}
};
vector<Node> graph;
void CreateVertex(const string& v)
{
Node n;
n.vertex = v;
n.adj = 0;
bool bfind = false;
if( find(graph.begin(), graph.end(), n) == graph.end() ) // 없
graph.push_back(n);
}
void link(const string& from, const string& to)
{
Node s;
s.vertex = from;
vector<Node>::iterator fromiter = find(graph.begin(), graph.end(), s);
Node* p = new Node;
p->vertex = to;
p->adj = fromiter->adj;
fromiter->adj = p;
}
int sina;
int non;
int saram;
int mymin = 9999999;
map<string, bool> visit;
void dfs(const string& curnode, int mycount)
{
//해가 맞는가?
//아니면
//모든 경우에 대해 백트
visit[curnode] = true;
///cout << curnode << endl;
if(curnode == "Erdos, P.")
{
if (mycount < mymin)
mymin = mycount;
} else
{
Node s;
s.vertex = curnode;
Node* p = &(*find(graph.begin(), graph.end(), s));
while(p)
{
if(mymin > mycount )
{
if( p->adj && !visit[p->adj->vertex] )
dfs(p->adj->vertex, mycount + 1);
}
p = p->adj;
}
}
visit[curnode] = false;
}
int main()
{
fin >> sina;
for (int i = 1; i <= sina; i++)
{
//memset(graph, 0, sizeof(graph));
fin >> non >> saram;
//
char t;
while (fin.get(t) && t != '\n')
;
for (int j = 1; j <= non; j++)
{
char temp[1024];
fin.getline(temp, 1024);
int startpos = 0;
vector<string> v;
for (int i = 0; i < strlen(temp); i++)
{ // 문자열 파싱.
if (strncmp(&temp[i], ".,", 2) == 0 || strncmp(&temp[i], ".:", 2) == 0)
{
string strtemp;
strtemp.assign(&temp[startpos], &temp[i + 1]);
v.push_back(strtemp);
startpos = i + 3;
}
}
//이어주기
for (int z = 0; z < v.size(); z++)
{
for (int z2 = 0; z2 < v.size(); z2++)
{
if(z != z2)
{
CreateVertex(v[z]);
CreateVertex(v[z2]);
link(v[z], v[z2]);
//link(v[z2], v[z]);
}
}
}
}
//for(map<string, int>::iterator i = dic.begin(); i != dic.end(); i++)
// cout << i->first << i->second << endl;
//while (fin.get(t) && t != '\n');
cout << "Scenario " << i << endl;
char temp[1024];
for (int j = 1; j <= saram; j++)
{
fin.getline(temp, 1024);
mymin = numeric_limits<int>::max();
clock_t start = clock();
dfs(temp, 0);
//cout << clock() - start << endl;
if (mymin == numeric_limits<int>::max())
cout << temp << " " << "infinity" << endl;
else
cout << temp << " " << mymin << endl;
}
}
return 0;
}