#P17947. Cloud-Ascending Platform
Cloud-Ascending Platform
给定一个有 个顶点、 条边的无向图,边按输入顺序编号为 到 ,第 条边的权值为 。
回答 个询问。每个询问给定 :只保留编号在这个区间内的边,求所得图中所有桥的边权和,对 取模。
一条边是桥,当且仅当删除它会使图的连通分量数增加。图不一定连通。
输入格式
第一行三个整数 (,)。
接下来 行,每行三个整数 (,),表示一条无向边。
接下来 行,每行两个整数 ()。
图没有自环,但允许重边。重边按各自的输入编号视为不同的边。
输出格式
每个询问输出一行一个整数,表示答案对 取模后的值。
样例 1
输入
5 6 6
1 2 1
2 3 2
2 4 4
2 5 8
1 3 16
4 5 32
1 3
2 4
3 5
4 6
2 6
1 6
输出
7
14
28
56
18
0