Задача №114877. Путешествия во времени
В будущем, после изобретения машины времени, изучать историю стало намного проще, ведь можно просто переместиться в нужное прошлое и посмотреть, как все было на самом деле! Этим изобретением активно пользуется Василий Андреевич, профессор университета, изучающий устройство дорог Берляндии на протяжении Великой Дорожной Реформы.
В течение \(k\) последовательных лет из-за Великой Дорожной Реформы, проходившей в Берляндии, её система дорог регулярно менялась. В этой стране \(n\) городов, пронумерованных для удобства целыми числами от \(1\) до \(n\). В течение каждого года эти города были соединены \(n-1\) двусторонними дорогами, причем между любой парой городов существовал единственный путь по дорогам, не проходящий через один и тот же город дважды.
Каждый рабочий день Василий Андреевич выбирал пару городов \(s\), \(f\), перемещался по очереди в каждый год Великой Дорожной Реформы и совершал в нём путешествие из города \(s\) в город \(f\), посещая при этом все города по пути, включая \(s\) и \(f\). После этого он выписывал количество городов, которые были общими во всех \(k\) путешествиях в этот день.
К сожалению, ровно в тот день, когда он закончил изучение Великой Дорожной Реформы, совершив путешествие для каждой возможной пары городов \(s\) и \(f\), все записи историка потерялись. Остались карты системы дорог Берляндии в каждый из \(k\) лет Великой Дорожной Реформы.
Помогите Василию Андреевичу и восстановите числа, которые бы он выписал для всех возможных пар городов \(s\) и \(f\).
В первой строке находятся два целых числа \(n\) и \(k\) — количество городов Берляндии и количество лет, изучаемых Василием Андреевичем (\(1 \leq n, k \leq 500\)).
Далее следует \(k\) описаний систем дорог Берляндии в различные года в следующем формате: в \(n-1\) строке очередного описания находится два целых числа \(a\) и \(b\) — номера городов, соединенных очередной дорогой (\(1 \leq a, b \leq n\), \(a \neq b\)).
Гарантируется, что в каждом из \(k\) изучаемых лет в Берляндии от любого города до любого существовал единственный путь, не проходящий через один и тот же город дважды.
Выведите \(n\) строк по \(n\) чисел в каждой. В \(i\)-й строке \(j\)-е число должно быть равно числу, которое выпишет Василий Андреевич, если \(s=i\) и \(f=j\).
В первом тесте в Берляндии \(4\) города. Всего есть \(2\) года, в которые перемещался Василий Андреевич.
Рассмотрим, например, пару городов \(s = 1\) и \(f = 2\). Переместившись в первый год, Василий Андреевич посетит города \(1\), \(2\), \(3\), \(4\). Переместившись во второй год, Василий Андреевич посетит города \(1\), \(2\), \(4\). Таким образом, он посетит \(3\) города \(1\), \(2\), \(4\) во всех путешествиях и выпишет число \(3\) для этой пары городов.
Рассмотрим пару городов \(s = 3\) и \(f = 1\). Переместившись в первый год, Василий Андреевич посетит города \(1\), \(3\). Переместившись во второй год, Василий Андреевич посетит города \(1\), \(3\), \(4\). Таким образом, он посетит \(2\) города \(1\), \(3\) во всех путешествиях и выпишет число \(2\) для этой пары городов.
4 2 1 3 4 2 3 4 1 4 4 3 2 4
1 3 2 2 3 1 3 2 2 3 1 2 2 2 2 1
3 3 1 2 2 3 2 3 3 1 3 1 1 2
1 2 2 2 1 2 2 2 1