来自我们竞赛教练的魔改题面

【问题描述】

小 Y 作为一名优秀的信息学竞赛保送生，毕业后被分配到 Z 市城市建设规划局工作，刚毕业的他本来准备在 Z 市的现代化城镇建设中大展宏图，但是到了工作岗位上才发现屡屡不顺。每次城市改造出现的问题要么就是按部就班的按照已有的方案来执行，就算有一些棘手的问题，一般也交给局里的经验丰富的专家来完成，每次小 Y 提出的用计算机建模来处理问题的方法都被嗤之以鼻，因为小 Y 不过是纸上谈兵而已。

终于有一天，规划局局长被小 Y 弄烦了，而且刚好某区域的建设遇到了一个新的问题，刚好局里的老人都腾不出人手来处理，局里的新人也不能完成这个任务，于是局长就把这个任务交给小 Y 了。

原来 Z 市某片区域由于长期交通拥挤需要重新修建道路，本来这是一个很简单的问题，但是关键在于财政紧张，经费不够，所以规划局只能选择该区域的部分道路进行重建。先重建哪些道路呢？各个居民点的居民都认为自家门前的道路需要先重建，正当大家一筹莫展的时候，有人提出了应该根据每条道路的拥堵程度来选择重建的顺序，人们都觉得很合理，但是，关键是如何确定每条道路的拥挤度呢？

Y 市可以看做是一张由 n 个点，m 条边组成的有向图，由于 Y 市的人走路都喜欢走最短路，所以每次任意两个点 a,b 之间的最短路径是最拥挤的，其他 路就算再畅通也没人会走，当然，如果有多条最短路，那么这多条最短路都会被经过。那么一条道路的拥挤度就可以通过该区域中所有两点之间的最短路径 经过的次数来表示。比如：

我们设 d[i,j]表示(i,j)这条最短路的拥挤度：

d[1,3]=1 d[1,4]=1 d[1,5]=1 d[2,3]=1 d[2,4]=1 d[2,5]=1 d[3,4]=3 d[3,5]=3

1->4,2->4,3->4 的最短路都经过了边(3,4)，所以 d[3,4]=3

但是由于该区域的居名点以及道路繁多，交通复杂，所以计算每一条道路的拥挤度并不是一件简单的事情，但是工期很紧，必须很快做出选择。虽然小Y 曾经是一位优秀的 OIer，但是由于大学太颓废了，现在才发现以前学习的知识他都忘光了，于是他不得不求助于你，你能帮助他吗？

对于小 Y 来说，只需要计算出每一条道路的拥挤度就可以了。

该区域无重边，也没有自环。