4026 - 【AB-1】图

Alice 给了 Bob 一个有趣的有向图。

这个有向图是动态的。在第 0 秒, 该有向图由 n 个点 m 条边组成, 且从点 1 可以走到任意点。在第 i(1 \le i \le T) 秒, Alice 会给该有向图增加一条从 u_i 到 v_i 的边。

这个有向图是无环的。具体来说, 在任意时刻, 该有向图都不存在环。

每一秒钟 (包括第 0 秒), Bob 都会回答当前图以 1 为根的生成树的个数对 10^9 + 7 取模的结果。

定义一个有向图以 root 为根的生成树为: 选择有向图中的 (n−1) 条边,使得通过这些边, 从点 root 能到达所有点。

请你预测 Bob 的回答。

第一行 3 个数 n,m,T, 意义如题面所述。

接下来 m 行, 每行两个数 x,y, 表示第 0 秒时, 该有向图存在一条从 x 到 y 的边。

接下来 T 行, 每行一个二元组 (u,v), 第 i 个二元组描述第 i 秒时增加的边。

输出为 (T + 1) 行, 每行一个数, 即 Bob 的回答。

对于 20\% 的数据, 1 ≤ n,m,T ≤ 10。

对于 50\% 的数据, 1 ≤ n,m,T ≤ 2 × 10^3 。

对于另外 20\% 的数据, T = 0。

对于 100\% 的数据, 1 ≤ n,m,T ≤ 2 × 10^5 ,1 ≤ u_i ,v_i ,x,y ≤ n。