7793: BZOJ3793:魔法

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

一天,白神和他的伙伴喵喵一起走到了可以产生魔法的神奇世界。但是这个世界产生魔法有这样一个有趣的方法。在一个无向图,有N个城镇,M条道路,并且每一条道路有一个权值(不超过10^18 )。每次从1号城镇出发,随意一条有限长度的路径,一条路可以经过多次,所经过的边将权值xor起来,若xor值不为0,则算新产生一种魔法(一个xor值对应唯一的魔法)。注意:一条边经过几次,就要xor几次)。
喵喵觉得这样太没有意思了,就在想假如我删除一些边这个世界的魔法总数还会有多少呢?喵喵可不会一下删完,他会进行Q次删边操作,每次只会删除一条边,他想知道每删除一条边,剩余的魔法种数有多少。


输入格式

第一行3个整数,表示N个节点,M条边,之后删除Q次边。
接下来M行表示A B 之间有一条U权值的边
在接下来Q行,表示删除第编号为A的边


输出格式

一共Q+1行,每行一个整数。


样例输入

3 3 2
1 2 1
2 3 2
3 1 4
1
3

样例输出

5
2
0

提示

所有数据保证该无向图不含重边、自环。
所有数据保证不会有一条边被删除多次,即对于不同i和j,有Disi≠Disj
N ≤ 5000,M ≤ 20000,Q ≤20000,U≤10^18;


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: