Поліглоти-інтроверти
Перед початком чергової лекції на всесвітній конференції поліглотів учасники зібралися в невеликій кімнаті. Усього в кімнаті знаходиться n осіб, кожен з яких володіє деякими з k мов. Випадково всі вони виявилися інтровертами, тому віддають перевагу читанню книг замість спілкування з іншими учасниками.
Іноді, однак, один з учасників конференції наважується поділитися інформацією з іншим. Дві людини можуть поспілкуватися або безпосередньо, або через ланцюжок посередників. При безпосередньому спілкуванні двоє людей можуть обрати будь-яку мову, якою володіють обидва співрозмовники. При спілкуванні через ланцюжок посередників будь-які двоє сусідніх людей у ланцюжку повинні обрати мову, якою володіють обидва. Таким чином, той, хто хоче передати інформацію, розповість її першому посереднику, той передасть її другому, і так далі, поки інформація не дійде до адресата. Проте, коли відбувається спілкування якоюсь мовою, всі в кімнаті, хто знає цю мову, чують розмову і відволікаються від своєї книги. Той, хто передає інформацію, прагне потурбувати якомога менше людей, тому планує ланцюжок посередників так, щоб якомога менше людей відволіклося під час передачі інформації.
Знайдіть для кожної пари людей (A, B), скільки мінімально людей можна відволікти, щоб передати інформацію від A до B.
Вхідні дані
У першому рядку містяться два числа n і k - кількість людей у кімнаті та кількість різних мов, якими вони володіють (2 ≤ n ≤ 300, 1 ≤ k ≤ 300).
Наступні n рядків містять описи людей, i-й з цих рядків описує мови, які знає i-й чоловік, у наступному форматі: k[i] a[i1] a[i2] ... a[i,ki] - кількість мов і самі мови у порядку зростання номерів (1 ≤ k[i] ≤ k, 1 ≤ a[ij] ≤ k, a[ij] < a[i,j+1]).
Вихідні дані
Виведіть n рядків, у кожному по n чисел f[ij], розділених пробілами - мінімальна кількість людей, які відволічуться при оптимальному способі передачі інформації від i-ї людини до j-ї. На головній діагоналі повинні стояти нулі. Якщо передати інформацію від i-ї людини до j-ї неможливо, виведіть замість відповідного числа -1.