#D. 出题人准备的礼物

    传统题 2000ms 512MiB

出题人准备的礼物

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

出题人很喜欢八重神子,于是最后决定送给你 nn 只狐狸作为礼物。

狐狸都很傲娇,因此 nn 只狐狸中只有 mm单向的交流渠道,一个交流渠道 (u,v)(u, v) 表示一只狐狸 uu 可以对另一只狐狸 vv 说话。

这些交流渠道又分为两种,一种需要花费 1 mora,一种则不需要

当狐狸 uu 想要与狐狸 vv 说话时,狐狸 uu 需要把消息告诉与它有交流渠道的狐狸 x1x_1x1x_1 告诉狐狸 x2x_2 ,...,直到拥有通往狐狸 vv 的交流渠道的狐狸 xkx_k 告诉狐狸 vv ,而狐狸 uu 需要为本次交流付出所有交流渠道的花费。

狐狸都十分聪明,因此它们都会选择花费最少的路径,这个路径集合称为 (u,v)(u, v) 的交流路径。

定义中间商次数为一只狐狸被所有有序狐狸对的交流路径集合(不存在交流路径则不考虑)覆盖的次数。

现在,你想要知道每只狐狸的中间商次数。

注意

  1. (u,v)(u, v)(v,u)(v, u) 的交流路径不一定相同。
  2. (u,u)(u, u) 的交流路径就是狐狸 uu 自身,这条路径给 uu 提供 11 的中间商次数。
  3. (u,v)(u, v) 的交流路径可能有多条,每一条都给其上的每只狐狸提供 11 的中间商次数。
  4. 可能存在不能达成交流的狐狸 (u,v)(u, v)
  5. 保证不存在一个狐狸的集合,使得集合内的交流路径都是零花费。
  6. (u,v)(u, v) 之间可能存在多条交流渠道。

本题答案最后对 998244353 取模

输入格式

11 行共两个整数 n,mn, m ,表示狐狸的数量和交流渠道的数量。

2m+12\sim m+1 行,每行三个整数 u,v,wu, v, w ,表示从 uuvv 有一条交流渠道,花费为 w(w{0,1})w(w \in \{0, 1\})

输出格式

输出 nn 行,每行一个数,第 ii 行表示编号为 ii 的狐狸的中间商次数。

测试用例

样例输入

5 8
3 2 1
2 5 0
5 2 1
2 4 1
2 1 1
3 5 1
3 4 0
4 5 1

样例输出

5
12
7
8
11

数据范围

对于前 10%10\% 的数据, n10n \le 10;

对于前 20%20\% 的数据, n100n \le 100;

对于前 40%40\% 的数据, n1000,m5000n \le 1000, m \le 5000;

对于另 20%20\% 的数据,没有零花费的交流渠道;

对于 100%100\% 的数据, $1 \le n \le 1000, 1 \le m \le 50000, w \in \{0, 1\}$,保证不存在一个狐狸的集合,使得集合内的交流路径都是零花费。

[YDRS#002] 云斗杯 · 六月 Silver 组模拟赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2023-6-24 8:30
结束于
2023-6-24 19:00
持续时间
3.5 小时
主持人
参赛人数
103