Dynamic Telephone Network Connectivity

CCO Country is serviced by the unique telephone provider Domiton. There are \(N\) houses in CCO Country, numbered from \(1\) to \(N\). Each telephone line connects two different houses, and all telephone lines that have ever existed do not form a cycle (i.e. they always form a tree).

However, each telephone line is only available during a certain period. At a given moment, if there exists a path between two houses using the available telephone lines, these houses can communicate with each other.

You are given \(Q\) queries. Each query has one of the following formats:

• 1 x y: Add a telephone line between house \(x\) and \(y\). It is guaranteed that a telephone line between \(x\) and \(y\) has not been added previously.
• 2 x y: Remove the telephone line that currently exists between house \(x\) and \(y\).
• 3 t: For the last \(t\) queries, count the number of unordered house pairs which, in at least one state among these \(t+1\) states, can communicate with each other. More precisely, let \(G_q\) be the state of CCO Country after the \(q\)th query, and \(G_0\) be the state before any query. If the current query is the \(s\)th query, you must consider the states \(G_{s-t}, G_{s-t+1}, \ldots, G_s\) and count the number of pairs of houses that are connected in at least one of these states.

Note on encrypted test cases: For some test cases, the parameters \(x\), \(y\) and \(t\) are given in encrypted form. For an encrypted test case, the actual parameter is obtained by parameter ^= lastAnswer (using C++’s ^= operator), where lastAnswer is the answer to the previous type \(3\) query (if no type \(3\) query has occurred previously, then lastAnswer is considered to be 0).

Input/Output Formats: See the input and output description sections below.

inputFormat

The first line contains two integers \(N\) and \(Q\) — the number of houses and the number of queries.

The next \(Q\) lines each contain a query in one of the three formats as described above. For encrypted test cases, if a query is of type 1 or 2, then the parameters \(x\) and \(y\) are given as \(x \oplus lastAnswer\) and \(y \oplus lastAnswer\); if a query is of type 3, then \(t\) is given as \(t \oplus lastAnswer\), where \(\oplus\) denotes the bitwise XOR operation.

outputFormat

For each query of type 3, output the required count on a separate line.

sample

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

3
3