P3733 [HAOI2017] Eight Verticals and Eight Horizontals

The country of Anihc has $n$ cities, numbered from $1$ to $n$, with city $1$ being the capital. Initially, there are $m$ highways between cities. Each highway has a non-negative integer economic impact factor, and each highway connects two cities (the endpoints may be the same city). It is guaranteed that any two cities are mutually reachable via highways. The country is planning the "Eight Verticals and Eight Horizontals" high-speed railway program, which will build some high-speed railways. Each railway also connects two cities (the endpoints may be the same city) and has a non-negative integer economic impact factor. After this program is completed, the country plans to extend the "Belt and Road" to "Belt and Road and Ring" by adding an "Inland Cities Economic Ring," i.e., choosing a path that starts from the capital and follows a sequence of railways and highways, where each railway or highway may be traversed multiple times, and each city may be visited multiple times, finally returning to the capital. Let the GDP of the "Inland Cities Economic Ring" be the XOR of the economic impact factors of the railways and highways traversed along this path in order (an edge traversed multiple times is counted multiple times). Anihc is discussing the construction plan for "Eight Verticals and Eight Horizontals" and will keep modifying the plan. You are asked to report, in real time, the maximum possible GDP of the "Inland Cities Economic Ring" for the current plan. Initially, the plan contains no railways. There are the following $3$ types of operations: `Add x y z` Add a high-speed railway between cities $x$ and $y$ with economic impact factor $z$. If this is the $k$-th `Add` operation, then this railway is named railway $k$. `Cancel k` Cancel railway $k$ from the plan. It is guaranteed that railway $k$ exists at this moment. `Change k z` Change the economic impact factor of railway $k$ to $z$. It is guaranteed that railway $k$ exists at this moment.

The first line contains $3$ integers $n, m, Q$, denoting the number of cities, the number of highways, and the number of operations. The next $m$ lines each contain $3$ integers, describing a highway. The next $Q$ lines each contain one operation, in one of the following forms: `Add x y z`, `Cancel k`, or `Change k z`. Note: All economic impact factors in the input are given in binary, from the most significant bit to the least significant bit.

Output one integer on the first line: the maximum possible GDP of the "Inland Cities Economic Ring" if no railway is built. Then output $Q$ lines, each containing one integer, where the $i$-th line is the maximum possible GDP of the "Inland Cities Economic Ring" after performing the $i$-th operation with respect to the current plan. Note: All answers must be output in binary, from the most significant bit to the least significant bit.

Constraints and Notes. Let $len$ be the maximum number of bits among the binary representations of all economic impact factors. The testdata satisfies the following table: | Data Point | $n$ | $m$ | $Q$ | $len$ | Special Property | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $\leq 5$ | $\leq 8$ | $0$ | $\leq 31$ | | | 2 | $\leq 100$ | $= n + 1$ | $0$ | $\leq 100$ | | | 3 | $\leq 100$ | $\leq 100$ | $0$ | $\leq 100$ | | | 4 | $\leq 500$ | $\leq 500$ | $0$ | $\leq 1000$ | | | 5 | $\leq 100$ | $\leq 100$ | $\leq 100$ | $\leq 200$ | Only `Add` operations | | 6 | $\leq 500$ | $\leq 500$ | $\leq 200$ | $\leq 1000$ | | | 7 | $\leq 100$ | $\leq 100$ | $\leq 1000$ | $\leq 200$ | | | 8 | $\leq 500$ | $\leq 500$ | $\leq 1000$ | $\leq 1000$ | | | 9 | $\leq 500$ | $\leq 500$ | $\leq 1000$ | $\leq 1000$ | | | 10 | $\leq 500$ | $\leq 500$ | $\leq 1000$ | $\leq 1000$ | | For all testdata it is guaranteed that $1 \leq n, m \leq 500$, $0 \leq Q \leq 1000$, $1 \leq len \leq 1000$, $1 \leq x, y \leq n$. Moreover, the number of `Add` operations does not exceed $550$. There may be multiple highways or railways between two cities, and an edge may have both endpoints at the same city (i.e., multiedges and self-loops). Translated by ChatGPT 5