3706 - 反色刷

给一张无向图，边有黑白两种颜色，现在你有一堆反色刷，可以从任意点开始刷，经过若干条边后回到起点。 现在要询问至少需要多少个反色刷可以使这张图所有边都变成白色。 因为某种原因，边的颜色是会改变的，于是。。 需要支持以下操作： 1 x 把第x条边反色（编号从0~m-1） 2 询问当前图中最少需要多少个反色刷

Input

第一行两个整数n m表示这张图有n个点m条边 接下来m行 每行3个整数 u v c表示一条无向边和这条边的颜色(0为白色 1为黑色) 接下来一个整数q 表示有q个操作 接下来q行为操作 描述如上

Output

对于每个询问 输出一行一个整数 表示最少需要的反色刷个数 如果没有合法方案输出-1

Examples

Input

6 6
1 2 1
2 3 1
1 3 1
4 5 1
5 6 1
4 6 1
14
2
1 0
2
1 1
1 2
2
1 3
1 4
1 5
2
1 3
1 4
1 5
2

Output

2
-1
1
0
1

Hint

100% n,m,q <= 1000000, c < 2，没有重边自环

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题