Полиглоты-интроверты
Полиглоты-интроверты
Перед очередной лекцией на всемирной конференции полиглотов ее участники собрались в небольшой комнате. Всего в комнате n человек, каждый из которых разговаривает на некоторых из k языков. По стечению обстоятельств, все из них оказались интровертами, а поэтому общению с другими участниками предпочитают мирное прочтение книги.
Иногда, однако, один участник конференции решается-таки сообщить какую-то информацию другому. Два человека могут поговорить либо напрямую, либо через цепочку посредников. При общении напрямую два человека могут выбрать любой язык, которые знают оба собеседника. При общении через цепочку посредников любые два соседних человека в цепочке должны выбрать язык, на котором они будут говорить, среди тех, который знают оба собеседника. Таким образом, тот, кто хочет передать информацию, расскажет её первому посреднику, тот затем расскажет её второму посреднику, и так далее, пока информация не дойдёт до того, кому она предназначается. Однако, когда происходит общение на каком-то языке, все в комнате, кто знает этот язык, слышат разговор на знакомом языке и отвлекаются от своей книги. Тот, кто передает информацию, хочет потревожить как можно меньше людей, поэтому планирует цепочку посредников таким образом, чтобы как можно меньше людей отвлеклось во время передачи информации.
Найдите для каждой пары людей (A, B), какое минимальное людей можно отвлечь, чтобы передать информацию от A к B.
Входные данные
В первой строке содержатся два числа n и k - число людей в комнате и число различных языков, на которых они разговаривают (2 ≤ n ≤ 300, 1 ≤ k ≤ 300).
Следующие n строк содержат описания людей, i-я из этих строк описывает языки, которые знает i-й человек, в следующем формате: ki ai1 ai2 ... ai,ki - количество языков и сами языки в порядке возрастания номеров (1 ≤ ki ≤ k, 1 ≤ aij ≤ k, aij < ai,j+1).
Выходные данные
Выведите n строк, в каждой по n чисел fij, разделенных пробелами - минимальное количество людей, которые отвлекутся при оптимальном способе передаче информации от i-го человека к j-му. На главной диагонали должны стоять нули. Если передать информацию от i-го человека к j-му невозможно, выведите вместо соответствующего числа -1.
6 4 2 1 2 2 2 3 1 2 1 1 2 3 4 1 4
0 3 3 2 4 5 3 0 3 4 2 3 3 3 0 4 4 5 2 4 4 0 5 6 4 2 4 5 0 2 5 3 5 6 2 0
4 3 2 1 2 1 1 1 2 1 3
0 2 2 -1 2 0 3 -1 2 3 0 -1 -1 -1 -1 0