P17499 [ICPC 2026 Wuhan I] I Will Always Remember You

Given a directed acyclic graph $G$ with $n$ vertices and $m$ edges, and a color sequence $a_1,a_2,\cdots,a_n$ of length $n$, where $a_i$ denotes the initial color of vertex $i$. Let $S_i$ denote the set of all vertices reachable from vertex $i$ in graph $G$ (including vertex $i$ itself). Now, you need to process $q$ operations in order. The operations are of the following two types: - Given $x$ and $y$, change the color $a_x$ of vertex $x$ to $y$. - Given $x$, query the number of distinct colors among all vertices reachable from vertex $x$. That is, find the size of the set $\{a_j\mid j\in S_x\}$.

The first line contains two integers $n,m$ ($1 \le n \le 1.5\times10^5$, $0 \le m \le 3\times10^5$), representing the number of vertices and the number of edges in the graph, respectively. The second line contains $n$ integers $a_1,a_2,\cdots,a_n$ ($1 \le a_i \le n$), representing the initial color of each vertex. The next $m$ lines each contain two integers $u,v$ ($1 \le u,v \le n$), indicating that there is a directed edge from $u$ to $v$ in graph $G$. It is guaranteed that graph $G$ is a directed acyclic graph (DAG) and contains no multiple edges. The next line contains an integer $q$ ($1 \le q \le 1.5\times10^5$), representing the total number of operations. The next $q$ lines each describe an operation in one of the following two formats: - `1 x y`: Represents an update operation, changing the color $a_x$ to $y$ ($1 \le x,y \le n$). - `2 x`: Represents a query operation, querying the number of distinct colors reachable from vertex $x$ ($1 \le x \le n$).

For each operation of the second type, output a single line containing an integer representing the answer to the query.