408054: GYM102968 D Data Integrity

A data integrity technique is used to ensure that some data is recorded as intended. It is very important to be able to identify that some data was not transmitted correctly so that it can possibly be fixed.

Bob came up with a revolutionary way of storing data using an undirected graph with $$$N$$$ nodes. He will be storing data as labels on the edges, such that each label is an integer in $$$[0, VAL]$$$. Now, he is curious about the number of distinct data sets that he could possibly place on the graph.

He considers a data set to be valid if and only if for every cycle in the graph, the xor sum of the labels of edges forming that cycle is $$$0$$$.

Formally, a data set is valid if for every sequence of nodes $$$a_1, a_2, ..., a_n$$$ with $$$a_1 = a_n$$$ such that for every integer $$$i$$$ in $$$[1, n-1]$$$ there exists an edge $$$b_i$$$ connecting $$$a_i$$$ and $$$a_{i+1}$$$ then:

$$$label_{b_1} \oplus label_{b_2} \oplus ... \oplus label_{b_{n-1}} = 0$$$, where $$$\oplus$$$ is the exclusive or operator.

Initially, the graph has $$$M$$$ edges, but Bob likes to experiment, so he will modify the graph $$$Q$$$ times by either removing an edge or adding a new edge that isn't already in the graph. He would like you to help him find the number of distinct valid data sets that he could have for the initial configuration, as well as after each update.

The first line of the input contains $$$4$$$ integers $$$N,\ M,\ Q,\ VAL$$$: $$$1 \leq N \leq 10^5$$$, the number of nodes in the graph, $$$1 \leq M \leq 2*10^5$$$, the number of edges in the initial graph, $$$0 \leq Q \leq 10^5$$$, the number of queries and $$$1 \leq VAL \leq 10^{18}$$$, the maximum value of a label. It is guaranteed that $$$VAL = 2^k - 1$$$ for some integer $$$k$$$.

The next $$$M$$$ lines contain a pair of nodes $$$(u, v), u \neq v$$$, representing an edge in the initial graph. It is guaranteed there are no duplicate edges.

The next $$$Q$$$ lines contain a pair of nodes $$$(u, v), u \neq v$$$, representing the updates. If the edge is not in the graph, it should be inserted and otherwise it should be removed. The modifications applied also affect all future updates.

The output should contain $$$Q + 1$$$ integers representing the number of valid data sets for the initial graph as well as after each query, modulo $$$10^9 + 7$$$. Two data sets are considered distinct if there exists an edge such that its label's value differs among the two sets.

3 3 2 1
1 2
2 3
3 1
1 3
3 2

4
4
2

7 7 2 65535
1 2
2 3
3 1
1 4
5 6
6 7
7 5
4 1
4 6

496641140
582344008
496641140

In the first example, initially, the 4 possible data sets are $$$(0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0)$$$ After the first update, we are left with edges $$$1-2$$$ and $$$2-3$$$, the 4 possible data sets being $$$(0, 0), (0, 1), (1, 0), (1, 1)$$$. After the second update, we are left with just one edge that can be either $$$0$$$ or $$$1$$$.