A7140 | [Cnoi2020] 线形生物

后置数学知识

- 可能用到的幂级数求和 : 若 $x1$，则有 $\sum\limits_{i=1}^{\infty}\big(\frac{1}{x}\big)^i=\frac{1}{x}+\frac{1}{x^2}+\frac{1}{x^3}+\cdots=\frac{1}{x-1}$。
- 数学期望 : 随机试验中每次可能结果的概率乘以其结果的总和，反映随机变量平均取值的大小。
- 离散期望公式 : $E(x)=\sum\limits_{k=1}^{\infty}x_kp_k$。

数据范围与约定

对于 $100\%$ 的数据，保证：$id \in \{1,2,3,4,5\}$，$0 n,m \le 10^6$，$1 \le v_i \le u_i \le n$。

子任务「本题采用捆绑测试」

- Subtask1（$10\%$）: 返祖图中所有点都有自环且所有边均为自环(未画出)，总图形如 :


- Subtask2（$10\%$）: 返祖图中所有点均向且仅向自己的前驱连边，特别地，$1$ 号节点的前驱是 $1$ 号节点，总图形如 :


- Subtask3（$10\%$）: 返祖图中所有点均向且仅向 $1$ 号节点连边，总图形如 :


- Subtask4（$10\%$）: $n \le 100$，$m \le 1000$。

- Subtask5（$60\%$）: 无特殊限制。