Problem F: Erdös Numbers

Background 

The Hungarian Paul Erdös (1913-1996, speak as ``Ar-dish'') not only was one of the strangest mathematicians of the 20th century, he was also one of the most famous. He kept on publishing widely circulated papers up to a very high age and every mathematician having the honor of being a co-author to Erdös is well respected.

Not everybody got the chance to co-author a paper with Erdös, so many people were content if they managed to publish a paper with somebody who had published a scientific paper with Erdös. This gave rise to the so-called Erdös numbers. An author who has jointly published with Erdös had Erdös number 1. An author who had not published with Erdös but with somebody with Erdös number 1 obtained Erdös number 2, and so on.

Problem 

Today, nearly everybody wants to know which Erdös number he or she has. Your task is to write a program which computes Erdös numbers for a given set of scientists.

Input 

The first line of the input contains the number of scenarios.

The input for each scenario consists of a paper database and a list of names. It begins with the line

P N

where P and N are natural numbers. Following this line are P lines containing descriptions of papers (this is the paper database). A paper appears on a line by itself and is specified in the following way:

Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors matrices

Note that umlauts like `ö' are simply written as `o'. After the P papers follow N lines with names. Such a name line has the following format:

Martin, G.

Output 

For every scenario you are to print a line containing a string ``Scenario i" (where i is the number of the scenario) and the author names together with their Erdös number of all authors in the list of names. The authors should appear in the same order as they appear in the list of names. The Erdös number is based on the papers in the paper database of this scenario. Authors which do not have any relation to Erdös via the papers in the database have Erdös number ``infinity".

Sample Input 

1
4 3
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices 
Erdos, P., Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First oder derivates in structured programming
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures
Smith, M.N.
Hsueh, Z.
Chen, X.

Sample Output 

Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2

---

// 0.060 s by morris821028

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
using namespace std;

char s[100005];
int main() {
    int t, cases = 0;
    int n, m, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        while(getchar() != '\n');
        map<string, int> name;
        map<string, int>::iterator it;
        vector<short> g[5005];
        int buf[5005];
        name["Erdos, P."] = 0;
        int name_size = 0;
        while(n--) {
            gets(s);
            int pre_idx = 0, bidx = 0;
            for(i = 1; s[i]; i++) {
                if((s[i] == ',' || s[i] == ':') && s[i-1] == '.') {
                    char tmp = s[i];
                    s[i] = '\0';
                    it = name.find(s+pre_idx);
                    if(it == name.end()) {
                        name[s+pre_idx] = ++name_size;
                        buf[bidx++] = name_size;
                    } else {
                        buf[bidx++] = it->second;
                    }
                    s[i] = tmp;
                    pre_idx = i+2;
                    if(s[i] == ':')
                        break;
                }
            }
            for(i = 0; i < bidx; i++) {
                for(j = i+1; j < bidx; j++) {
                    g[buf[i]].push_back(buf[j]);
                    g[buf[j]].push_back(buf[i]);
                }
            }
        }
        int used[5005] = {}, dp[5005] = {}, x;
        used[0] = 1, dp[0] = 0;
        queue<int> Q;
        Q.push(0);
        while(!Q.empty()) {
            x = Q.front(), Q.pop();
            for(vector<short>::iterator it = g[x].begin();
                it != g[x].end(); it++) {
                if(used[*it] == 0) {
                    dp[*it] = dp[x]+1;
                    used[*it] = 1;
                    Q.push(*it);
                }
            }
        }
        printf("Scenario %d\n", ++cases);
        while(m--) {
            gets(s);
            it = name.find(s);
            printf("%s ", s);
            if(it == name.end())
                puts("infinity");
            else if(!used[it->second])
                puts("infinity");
            else
                printf("%d\n", dp[it->second]);        }
    }
    return 0;
}