#10. 随机游走 内存限制：512 MiB 时间限制：2000 ms 标准输入输出 题目类型：传统 评测方式：文本比较 上传者： zhouyuyang 提交 提交记录 统计 测试数据 讨论 题目描述 给定一张 个点， 条边的有向图。可能有自环和重边。

保证对于任意一对节点 ,满足存在一条 到 的路径。

现在ysgh想要在这张图上随机游走。每次他会等概率随机选择当前点的一条出边，并且沿着出边移动。

ysgh想要知道，如果他从点 出发，下一次到达节点 期望要走多少条边。(注意如果 ，此时初始状态不会结束,ysgh会随机选择一条出边游走) 输入格式 第一行两个数 。

接下来 行，每行两个数字 ，表示一条有向边。 输出格式 行，第 行第 个数字表示ysgh从点 出发，下一次到达节点 期望要走多少条边。对 取模。 样例 样例输入1

复制3 4 1 2 2 3 3 1 3 2 样例输出1

复制5 1 2 4 499122179 1 3 499122178 499122179 数据范围与提示 对于前 的数据，满足 。

对于所有测试数据，满足 。

保证所有测试数据中图在合法的情况下随机生成。

社论见王修涵19年集训队论文。