Заданий неорієнтований граф без петель та кратних ребер, в якого \(N\) вершин, та \(M\) ребер. В кожної вершини є колір. Необхідно опрацювати \(Q\) запитів. Запити бувають двох типів:

\(1\) \(V\) \(C\) – перефартувати вершину \(V\) в колір \(C\)

\(2\) \(V\) – обчислити кількість різних кольорів у сусідів вершини \(V\).

Вхідні дані

В першому рядку дано три цілих числа \(N,M,Q\) (\(1 \le N \le 10^5\), \(1 \le M,Q \le 2*10^5\)).

В другому рядку через пробіл задано \(N\) цілих чисел - кольори вершин. (\(1 \le Ci \le N\))

В наступних \(M\) рядках задано по 2 цілих числа \(U,V\) - номера вершин які з'єднує чергове ребро.

В наступних \(Q\) рядках задані запити. Кожен запит має один з двох типів:

\(1\) \(V\) \(C\) – перефарбувати вершину \(V\) в колір \(C\) (\(1 \le C \le N\))

\(2\) \(V\) – обчислити кількість ріхних кольорів у сусідів вершини \(V\)

Вихідні дані

Для кожного запиту другого типу виведіть в окремому рядку відповідь на нього.

Обмеження

• \(1≤t≤2⋅10^5\)
• \(1≤n≤2⋅10^5\)
• \(1≤x_i ​ ≤10^9\)
• сума всіх \(n\) не перевищує \(2⋅10^5\)

Приклад вхідних даних

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

Приклад вихідних даних

3
2