Background

Note: You can get more sample tests in the attachments.

Problem Description

There is an undirected graph with $N$ vertices, numbered $0 \sim N-1$. There are no self-loops in this graph. Initially, the graph has no edges.

You are given $T$ edge sets $E_0,\ldots,E_{T-1}$. For $u=0,1,\cdots,T-1$, at time $u+0.5$, take the XOR (symmetric difference) of $E_u$ and the current edge set of the graph. In other words, let the current edge set be $E$, and for every $e\in E_u$:

• If $e$ is in $E$, delete $e$ from $E$.
• Otherwise, add $e$ to $E$.

For a non-negative integer $t$ and two vertices $a,b$, we say that $a,b$ are connected at time $\boldsymbol{t}$ if and only if at time $t$ there exists a path connecting $a$ and $b$. In particular, if $a=b$, then by definition this statement is always true for any $t$.

Furthermore, for integers $0\le l\le r\le T$ and two vertices $a,b$, we say that $a,b$ are connected during the time interval $\boldsymbol{[l,r]}$ if and only if $a,b$ are connected at every time $t=l,l+1,\ldots,r$.

There are $Q$ queries. Each query gives $x,l,r$. Return the number of vertices $y$ such that $x,y$ are connected during the time interval $[l,r]$ ($0\le x\le N-1$, $0\le l\le r\le T$, $0\le y\le N-1$).

Implementation Details

This is a functional interactive problem. You do not need to, and should not, implement the main function.

You should implement the following function:

vector<int> count_computers(int N, int T, int Q, vector<vector<array<int, 2>>> E, vector<array<int, 3>> F)

• $E$: an array storing the edge sets. The size of $E$ is $T$. Each $E[i]$ is a non-empty edge array representing the set $E_i$. Each edge is given as an array of size $2$, with elements $[a,b]$ in order, representing an edge connecting vertices $a$ and $b$.
• $F$: an array storing the queries. The size of $F$ is $Q$. For any $0\le i\le Q-1$, $F[i]$ represents the $i$-th query. Each query is given as an array of size $3$, with elements $[x,l,r]$ in order, where $x$ is a vertex and $[l,r]$ is a time interval.
• Return an array $R$ of size $Q$. For any $0\le j\le Q-1$, $R[j]$ is the answer to the $j$-th query.
• This function is called exactly once.

Your source code must not call any input/output functions.

Input Format

The input format of the sample grader program is as follows. $|E_i|$ denotes the size of the set $E_i$, and $S = \sum_{0 \le i \le T-1} |E_i|$.

• Line $1$: $N$ $T$ $Q$.
• For all $0 \le i \le T-1$:
  • Line $2 + \sum_{0 \le j < i} (1 + |E_j|)$: $|E_i|$.
  • Line $2 + \sum_{0 \le j < i} (1 + |E_j|) + k$ ($0 \le k < |E_i| - 1$): $a \ b$ (the two endpoints of the $k$-th edge in $E_i$).
• Line $2 + S + T + i$ ($0 \le i \le Q - 1$): $x \ l \ r$ (each element of $F[i]$).

Output Format

The sample grader program outputs the answers in the following format:

• Line $1 + i$ ($0 \le i \le Q - 1$): $R[i]$.

4 5 7
2
0 1
1 2
2
2 3
1 3
2
0 1
0 3
4
0 1
1 2
0 3
2 3
1
1 3
1 1 1
2 2 2
3 3 3
0 0 5
2 1 3
1 1 4
3 2 3

3
4
4
1
3
2
4

Hint

Constraints

• $2\le N\le 100\, 000$.
• $1\le T\le 100\, 000$.
• $1\le Q\le 250\, 000$.
• $E_i$ is an edge set, and all edges inside it are pairwise distinct.
• Let $S=\sum_{0\le i\lt T-1} |E_i|$, then $S\le 100\, 000$.
• For every edge $[a,b]$ given in the input, $0\le a\lt b\le N-1$.
• For every query given in the input, $0\le x\le N-1,0\le l\le r\le T$.

Subtasks

Sample

Consider the following call.

count_computers(4, 5, 7, [[[0, 1], [1, 2]], [[2, 3], [1, 3]], [[0, 1], [0, 3]], [[0, 1], [1, 2], [0, 3], [2, 3]], [[1, 3]], [[1, 1], [2, 2], [3, 3], [0, 0], [0, 5]], [[2, 1, 3], [1, 1, 4], [3, 2, 3]]])

There are $4$ vertices in the graph.

At each time, the graph is as follows:

• At time $0$: $0$ edges.
• At time $1$: $2$ edges: $(0, 1), (1, 2)$.
• At time $2$: $4$ edges: $(0, 1), (1, 2), (2, 3), (1, 3)$.
• At time $3$: $4$ edges: $(1, 2), (2, 3), (1, 3), (0, 3)$.
• At time $4$: $2$ edges: $(0, 1), (1, 3)$.
• At time $5$: $1$ edge: $(0, 1)$.

A total of $7$ queries are given:

• Query $0$: At time $1$, vertex $1$ is connected to the set $\{0, 1, 2\}$.
• Query $1$: At time $2$, vertex $2$ is connected to the set $\{0, 1, 2, 3\}$.
• Query $2$: At time $3$, vertex $3$ is connected to the set $\{0, 1, 2, 3\}$.
• Query $3$: Since there are no edges at time $0$, from time $0$ to $5$, vertex $0$ is only connected to vertex $0$.
• Query $4$: From time $1$ to $3$, vertex $2$ is connected to the set $\{0, 1, 2\}$.
• Query $5$: From time $1$ to $4$, vertex $1$ is connected to the set $\{0, 1\}$.
• Query $6$: From time $2$ to $3$, vertex $3$ is connected to the set $\{0, 1, 2, 3\}$.

Therefore, the function should return $[3, 4, 4, 1, 3, 2, 4]$.

You can get more sample tests in the attachments.

Translated by ChatGPT 5