Computer Science

Computer science studies ways of solving real-world problems using computers and related technology, and it covers a great many topics. One of its recent success stories is organizing and searching information — just think of how web search has changed everyone's life. Here we explore a very simple web search engine.

You are given several documents made of words and hyperlinks (in a format simpler than HTML). You are also given queries (one word each) and must find the most relevant results. A page $P$ is relevant either because (1) the query word appears in $P$, or because (2) the query word appears in a page that links to $P$, close to that hyperlink.

Scoring. Let $q$ be the query word.

• $P$ earns one point for every occurrence of $q$ in $P$.
• For every hyperlink $L$ that goes from some page $P'$ to $P$, and for every occurrence of $q$ in $P'$ at word distance $d$ from $L$, page $P$ earns $\max(4 - d, 0)$ points — that is, $4 - d$ points when $d < 4$, and $0$ points otherwise.

The displayed word of a hyperlink is itself a word of the document: it counts as an occurrence when it equals $q$, and it occupies its own position when distances are measured. In particular, if $q$ is the displayed word of the hyperlink $L$ itself, that occurrence is at distance $d = 0$ and is worth $4$ points. Distances are counted in words over the whole document, ignoring line breaks. The same occurrence in $P'$ may be counted several times if it is close to several hyperlinks pointing to $P$.

Note: reason (2) is often the more important one. What other pages say about you when they link to you is frequently a better description than what you say about yourself — partly because a page could otherwise spam its own text, and partly because a page often does not contain every relevant term.

The first line contains an integer $K \ge 1$, the number of data sets. It is followed by $K$ data sets of the following form.

The first line of a data set contains two integers $m$ and $n$: the number of queries and the number of web pages. Both are between $1$ and $100$.

The next $m$ lines each contain one query: a single word of at most $20$ lowercase letters.

Then come the descriptions of the $n$ web pages. The description of page $i$ starts with a line containing the number $\ell_i$ of lines that page $i$ consists of (between $1$ and $100$), followed by $\ell_i$ lines of text of at most $255$ characters each. Each line of text is a sequence of words separated by single spaces. Every word consists only of lowercase letters and is at most $20$ characters long.

Some words are hyperlinks, written by enclosing the displayed word together with the target page number in square brackets. For example, [usc,3] is a hyperlink whose displayed word is usc and whose target is page $3$. The target is always a valid page between $1$ and $n$, and there are never self-links (a page never links to itself).

For each data set, first print a line Data Set x:, where $x$ is the number of the data set (starting from $1$). Then, for each query in order, print the page with the highest score on its own line. If several pages share the highest score, print all of them on one line, separated by single spaces, in increasing order of page number.