P16252 [蓝桥杯 2026 省研究生组] 通信链路

小蓝是一家通信网络公司的工作人员，他正在进行统计工作。 通信网络由 $ n $ 个中继站和 $ m $ 条通信链路构成，信息通过一条链路需要花费一定的时间，信息从一个中继站经过若干条链路传输到另一个中继站，总延迟是各链路的花费时间之和。由于一条链路的容量有限，假设一条链路连接中继站 $ x $ 和 $ y $，如果信息从 $ x $ 传递到 $ y $ 花费时间 $ w $，那么信息从 $ y $ 传递到 $ x $ 则需花费时间 $ 20 - w $。 小蓝只关心总延迟的个位数字是多少。对于一对不同的中继站对 $ (u, v) $，如果信息能够通过若干条链路从 $ u $ 传输到 $ v $，且总延迟的个位数字是 $ k $，则小蓝称 $ (u, v) $ 是 $ k $ 和谐的。由于从 $ u $ 到 $ v $ 的延迟和从 $ v $ 到 $ u $ 的延迟可能不同，$ (u, v) $ 和 $ (v, u) $ 应当认为是不同的中继站对，且像 $ (u, u) $ 这样的中继站对是不合法的。 现在，小蓝希望你帮他求出，0 和谐，1 和谐，2 和谐，…，9 和谐的中继站对各有多少个。

输入包含若干行，第一行两个正整数 $ n, m $，分别表示中继站个数和链路条数。 接下来 $ m $ 行，每行三个正整数 $ x_i, y_i, w_i $，表示中继站 $ x_i, y_i $ 之间有一条链路，且信息从这条链路上从 $ x_i $ 传递到 $ y_i $ 需要时间 $ w_i $；从 $ y_i $ 传递到 $ x_i $ 需要时间 $ 20 - w_i $。 给定的网络可能包含重边或自环。

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

### 【样例说明】 | 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) | 上表列出了各个 $ x $ 和谐的中继站对，例如存在一种通信方案 $ 1 \to 2 \to 3 \to 1 \to 2 $ 的总延迟是 $ 6 $，个位数是 $ 6 $，所以点对 $ (1,2) $ 是 $ 6 $ 和谐的。 一个中继站对对于不同的 $ x $ 和 $ y $，可能既是 $ x $ 和谐的，又是 $ y $ 和谐的。对于一个中继站对，可能有多种通信方案的总延迟个位数都为 $ x $，但应当只被统计一次，例如 $ 1 \to 3 \to 2 $ 的总延迟是 $ 16 $，也满足个位数是 $ 6 $，但 $ (1,2) $ 在 $ 6 $ 和谐中只被统计一次。 ### 【评测用例规模与约定】 对于 $ 30\% $ 的数据，$ w_i = 10 $； 对于另 $ 20\% $ 的数据，$ m = n - 1, x_i = i, y_i = i + 1 $； 对于另 $ 20\% $ 的数据，$ m = n - 1 $ 且任意两个中继站之间都一定能通过链路传输信息； 对于 $ 100\% $ 的数据，$ 2 \leq n \leq 100000, 0 \leq m \leq 200000, 1 \leq x_i, y_i \leq n, 1 \leq w_i < 20 $。