Polyglots-Introverts
Before the next lecture at the World Conference of Polyglots, the participants have gathered in a small room. There are n people present, each speaking a selection of the k available languages. Interestingly, all attendees are introverts, preferring to read books quietly rather than engage in conversation.
Occasionally, a participant may wish to share information with another. Communication can occur either directly or through a series of intermediaries. For direct communication, two people can choose any language they both understand. When using intermediaries, each pair in the chain must select a common language to converse in. The information is passed from the sender to the first intermediary, then to the next, and so on, until it reaches the recipient. However, when a conversation takes place in a particular language, everyone in the room who understands that language will overhear and be distracted from their reading. Therefore, the sender aims to minimize the number of people distracted by carefully planning the chain of intermediaries.
Your task is to determine, for each pair of people (A, B), the minimum number of people who will be distracted when transferring information from A to B.
Input
The first line contains two integers n and k, representing the number of people in the room and the number of different languages spoken, respectively (2 ≤ n ≤ 300, 1 ≤ k ≤ 300).
The following n lines describe the languages known by each person. The i-th line provides the languages known by the i-th person in the format: k[i] a[i1] a[i2] ... a[i,ki] - where k[i] is the number of languages known, followed by the languages themselves in ascending order (1 ≤ k[i] ≤ k, 1 ≤ a[ij] ≤ k, a[ij] < a[i,j+1]).
Output
Output n lines, each containing n numbers f[ij], separated by spaces. Each number represents the minimum number of people who will be distracted when optimally transferring information from the i-th person to the j-th. The main diagonal should contain zeros. If it is impossible to transfer information from the i-th person to the j-th, output -1 instead of the corresponding number.