#P18093. I Will Always Remember You

I Will Always Remember You

I Will Always Remember You

题目描述

给定一个有 nn 个顶点、mm 条边的有向无环图。顶点 ii 的初始颜色为 aia_i。

按顺序处理 qq 次操作:

  • 1 x y:把顶点 xx 的颜色改为 yy。
  • 2 x:查询从 xx 出发能够到达的所有顶点中,有多少种不同颜色。可达顶点包含 xx 自身。

输入格式

第一行输入 n,mn,m。第二行输入 a1,…,ana_1,\ldots,a_n。

接下来 mm 行,每行两个整数 u,vu,v,表示有向边 u→vu\to v。

下一行输入 qq,随后 qq 行按照上述格式给出操作。

输出格式

对每次第二类操作输出一行,一个整数,表示答案。

数据范围

1≤n,q≤1500001\le n,q\le150000,0≤m≤3000000\le m\le300000,1≤ai,x,y,u,v≤n1\le a_i,x,y,u,v\le n。图无环、无重边。顶点编号不保证是拓扑序,图也不要求连通。

样例 1

输入

9 14
8 4 2 3 5 2 2 4 7
3 5
8 9
4 5
5 8
6 8
3 8
1 4
2 9
2 4
2 8
1 3
7 9
1 8
5 7
10
1 6 4
1 3 3
2 1
2 3
1 4 3
1 8 5
1 8 7
2 7
2 2
2 9

输出

6
5
2
5
1