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

给定一个 $n$ 个点 $m$ 条边的有向无环图 $G$，以及一个长度为 $n$ 的颜色序列 $a_1,a_2,\cdots,a_n$，其中 $a_i$ 表示点 $i$ 的初始颜色。 记 $S_i$ 表示在图 $G$ 上从点 $i$ 出发能够到达的所有点构成的集合（包括点 $i$ 自身）。 现在需要依次处理 $q$ 次操作，操作分为以下两种： - 给定 $x$ 和 $y$，将点 $x$ 的颜色 $a_x$ 修改为 $y$。 - 给定 $x$，查询从点 $x$ 出发能够到达的所有点中，一共有多少种不同的颜色。即求集合 $\{a_j\mid j\in S_x\}$ 的大小。

第一行包含两个整数 $n,m$（$1 \le n \le 1.5\times10^5$，$0 \le m \le 3\times10^5$），分别表示图的节点数和边数。 第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$（$1 \le a_i \le n$），表示每个节点的初始颜色。 接下来 $m$ 行，每行包含两个整数 $u,v$（$1 \le u,v \le n$），表示图 $G$ 中存在一条从 $u$ 指向 $v$ 的有向边。保证图 $G$ 是一个有向无环图，且不存在重边。 接下来一行包含一个整数 $q$（$1 \le q \le 1.5\times10^5$），表示操作的总次数。 接下来 $q$ 行，每行描述一次操作，格式为以下两种之一： - `1 x y`：表示一次修改操作，将 $a_x$ 的颜色修改为 $y$（$1 \le x,y \le n$）。 - `2 x`：表示一次查询操作，查询从点 $x$（$1 \le x \le n$）出发能到达的颜色种类数。

对于每个第二种操作，输出一行包含一个整数，表示对应查询的答案。