Erdős Numbers

Among researchers there is a well-known concept called the Erdős number, named after the famous mathematician Paul Erdős. A person's Erdős number is the smallest value determined by the following rules:

• Erdős has Erdős number 0.
• If you have co-authored a paper with Erdős, your Erdős number is 1.
• If you have co-authored a paper with someone whose Erdős number is 1, your Erdős number is 2, and so on.

If none of the rules apply, the Erdős number is infinite. A smaller Erdős number reflects a closer co-authorship link to Erdős.

However, this classic definition ignores the passage of time. For example, suppose Erdős co-authored a paper with A, and A co-authored a paper with B. Then A gets 1 and B gets 2. But A may have written the paper with B early in their career and the paper with Erdős much later. Is it then fair for B to already have 2? The classic definition only counts the length of the shortest chain of papers linking a person to Erdős.

To account for the effect of time, we add the following requirement: the publication years along a chain that starts from Erdős must form a strictly increasing sequence. That is, each next paper in the chain must have been published in a strictly later year than the previous one.

Given a list of publications, answer queries of the form: as of a given year, what is the Erdős number of a given person? under the requirement above. A person's Erdős number as of year $Y$ is the length (number of papers) of the shortest valid chain from Erdős to that person that uses only papers published in year $Y$ or earlier and whose years strictly increase. If no such chain exists, the answer is infinite.

The first line contains an integer $z$ — the number of data sets that follow.

Each data set is described as follows:

• The first line contains two integers $p$ and $q$ ($1 \le p, q \le 100000$): the number of publications and the number of queries.
• Each of the next $p$ lines describes one publication: an integer $y$ ($1913 \le y \le 2005$), the publication year, followed by the space-separated surnames of all of its (distinct) co-authors. Each publication has between $2$ and $10$ authors. A surname is a string of English letters whose first letter is uppercase and the rest lowercase, with length between $1$ and $10$.
• Each of the next $q$ lines describes one query: an integer $y$, the year being asked about, followed by a space and the surname of a person (same surname format as above).

The number of distinct authors in a data set does not exceed $100000$. Paul Erdős appears in the input under the surname Erdos.

For each data set, print $q$ lines, one per query in the given order. For each query, print the Erdős number of the given person as of the queried year. If that Erdős number is infinite, print NIESKONCZONA (the Polish word for "infinite").