logo AlgoBeat OnlineJudge
登录 注册

#216316. [蓝桥杯 2026 省研究生组] 通信链路

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

小蓝是一家通信网络公司的工作人员,他正在进行统计工作。

通信网络由 个中继站和 条通信链路构成,信息通过一条链路需要花费一定的时间,信息从一个中继站经过若干条链路传输到另一个中继站,总延迟是各链路的花费时间之和。由于一条链路的容量有限,假设一条链路连接中继站 ,如果信息从 传递到 花费时间 ,那么信息从 传递到 则需花费时间

小蓝只关心总延迟的个位数字是多少。对于一对不同的中继站对 ,如果信息能够通过若干条链路从 传输到 ,且总延迟的个位数字是 ,则小蓝称 和谐的。由于从 的延迟和从 的延迟可能不同, 应当认为是不同的中继站对,且像 这样的中继站对是不合法的。

现在,小蓝希望你帮他求出,0 和谐,1 和谐,2 和谐,…,9 和谐的中继站对各有多少个。

输入格式

输入包含若干行,第一行两个正整数 ,分别表示中继站个数和链路条数。

接下来 行,每行三个正整数 ,表示中继站 之间有一条链路,且信息从这条链路上从 传递到 需要时间 ;从 传递到 需要时间

给定的网络可能包含重边或自环。

输出格式

输出共 10 行,每行一个正整数,依次表示 0 和谐,1 和谐,…,9 和谐的中继站对的数量。

样例

样例输入 1

3 3
1 2 1
2 3 2
3 1 2

样例输出 1

0
1
2
2
1
0
1
2
2
1

数据范围与提示

【样例说明】

0 1 2 3 4 5 6 7 8 9
/ (1,2) (2,3),(3,1) (1,3),(3,2) (2,1) / (1,2) (2,3),(3,1) (1,3),(3,2) (2,1)

上表列出了各个 和谐的中继站对,例如存在一种通信方案 的总延迟是 ,个位数是 ,所以点对 和谐的。

一个中继站对对于不同的 ,可能既是 和谐的,又是 和谐的。对于一个中继站对,可能有多种通信方案的总延迟个位数都为 ,但应当只被统计一次,例如 的总延迟是 ,也满足个位数是 ,但 和谐中只被统计一次。

【评测用例规模与约定】

对于 的数据,

对于另 的数据,

对于另 的数据, 且任意两个中继站之间都一定能通过链路传输信息;

对于 的数据,