409396: GYM103496 I Ice Breaker

I. Ice Breakertime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

During a party, Cindy encountered Alice by herself in a corner of the room, not talking to anyone, but just watching other people interact. Cindy asked Alice what was wrong, and Alice explained that she found it hard to strike up conversations with random people. Cindy explained to Alice that talking with people is easy if you can find a suitable ice breaker to get over the original awkwardness. Since Alice was on the student council, she probably knew a lot people, so Cindy said that a good ice breaker for her would be to talk about a common friend that she and her conversation partner both knew.

Alice, nervous and pedantic, asked Cindy to clarify what it meant to know someone. After a two-hour long philosophical discussion about the Epiphany of the Face and "How can we say that we know anything???", Cindy offered the following simplified definition (for party purposes).

• In their school, there are many different organizations, and a student can join up to four different orgs.
• Two people know each other if they are part of the same club.
  • Example: Alice and Cindy are both part of the Japanese Culture Org. So, Alice and Cindy know each other.

Is this an imperfect definition of know? Well, yes. If a student hasn't joined any organizations, then by our definition, that person doesn't know anyone. But this is just an ice breaker, after all, so it's fine that it's not perfect!

Alice still seemed nervous, so Cindy decided to spend the rest of the party talking with her, instead of pushing her to talk to strangers. The two of them developed a party game.

Alice, as part of the Student Council, knows the names of all the students in the school, as well as the full rosters of all orgs in the school. Cindy first names some classmate. Alice should say a sequence of names, starting with herself, Alice. Each next name that she mentions must belong to someone who knows the previous person in the sequence. The goal is to try to reach the classmate that Cindy named using the shortest sequence possible. The number of names (other than Alice) in the shortest such sequence to that classmate is that person's Alice number. A smaller Alice number means that, in a sense, Alice is a "closer acquaintance" of that person.

If the task is impossible for some person, then their Alice number is $$$-1$$$. Also, by definition, the Alice number of Alice is $$$0$$$.

The next day, Alice thought it was fun enough to turn into a programming problem. Can you replicate her success?

Input

The first line of input contains two space-separated integers $$$n$$$ and $$$m$$$, the number of students in Alice's school, and the number of different orgs at Alice's school.

Next, a line containing $$$n$$$ space-separated words, the full list of names of the students in Alice's school. Exactly one of these will be Alice.

Each org is then described in the following manner.

• First, a line containing a single integer $$$k$$$, the number of students in this org. Each org has at least one member.
• Then, a line containing $$$k$$$ space-separated names, the students in this org, in some order.

Contestants are recommended to use fast methods of input and output for this problem. It is recommended that Python users submit to PyPy for this problem.

Output

Output a single line containing $$$n$$$ space-separated integers, the Alice numbers of the students in Alice's school, listed in the same order that the students' names were given in the input.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline \text{Alice always appears in the list of students' names.} \\ \text{Each name will appear in no more than four different orgs.} \\ \text{No two students have the same name.} \\ \text{The names in each org roster are unique.} \\ \text{Each student's name consists of at most $5$ upper or lowercase English letters.} \\ \text{The names are case sensitive.} \\ 1 \leq n \leq 10^5 \\ 1 \leq m \leq 10^5 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline

1 & \mathbf{40} & 1 \leq n \leq 40 \\ && 1 \leq m \leq 40 \\ \hline

2 & \mathbf{40} & 1 \leq n \leq 520 \\ && 1 \leq m \leq 520 \\ \hline

4 & \mathbf{20} & \text{No further constraints.} \\ \hline

\end{array}\\

\end{align*}$$$$$$

ExamplesInput

10 4
Alice Bob Cindy Dani Eve Franz Gabi Hans Isa Jules
3
Alice Bob Cindy
2
Cindy Dani
4
Dani Eve Franz Gabi
2
Hans Isa

Output

0 1 1 2 3 3 3 -1 -1 -1

Input

10 4
Alice Bob Cindy Dani Eve Franz Gabi Hans Isa Jules
3
Alice Bob Cindy
2
Bob Dani
2
Dani Eve
2
Cindy Eve

Output

0 1 1 2 2 -1 -1 -1 -1 -1

Note

In the first sample input, for Eve, Alice can consider the sequence, $$$$$$ \texttt{Alice$\to$Cindy$\to$Dani$\to$Eve}. $$$$$$ This sequence uses three names (other than Alice): Cindy, Dani, Eve. No shorter sequence exists. Thus, Eve has an Alice number of $$$3$$$.

For the second sample input, for Eve, Alice can consider the sequence, $$$$$$ \texttt{Alice$\to$Bob$\to$Dani$\to$Eve}, $$$$$$ which has $$$3$$$ names (other than Alice). However, the Alice number of Eve is not actually $$$3$$$, because a shorter sequence exists, $$$$$$ \texttt{Alice$\to$Cindy$\to$Eve}. $$$$$$ The Alice number of Eve here is actually $$$2$$$.