방향 비순환 그래프

최근 Rikka는 방향 비순환 그래프(DAG)를 다루는 자료 구조에 큰 관심을 갖게 되었다. 그녀는 가중 체인 분해 같은 트리 기반의 고전 알고리즘을 DAG 버전으로 확장하면 정말 멋질 것이라고 꿈꾼다.

이제 그녀는 간단한 문제를 하나 떠올렸고, 이 문제를 함께 풀자며 당신을 초대한다.

정점 $n$개와 간선 $m$개로 이루어진 DAG $G$가 주어진다. 각 정점 $u$는 음이 아닌 정수 값 $\mathit{val}_u$를 가진다. 처음에는 모든 값이 $0$이다.

Rikka는 다음 세 종류의 연산을 $q$번 수행하려고 한다.

1. $u$와 $x$가 주어지면, $u$에서 도달 가능한 모든 $v$에 대해 $\mathit{val}_v$를 $x$로 설정한다.
2. $u$와 $x$가 주어지면, $u$에서 도달 가능한 모든 $v$에 대해 $\mathit{val}_v$를 $\min\{\mathit{val}_v, x\}$로 설정한다.
3. $u$가 주어지면, 현재의 $\mathit{val}_u$를 출력한다.

정점 $v$가 $u$에서 도달 가능하다는 것은, $u$에서 시작해 $v$에서 끝나는 경로가 존재한다는 뜻이다. 경로는 정점 나열 $p_1, p_2, \ldots, p_k$이며, 각 $i = 1, 2, \ldots, k-1$에 대해 $(p_i, p_{i+1}) \in G$를 만족한다.

이 연산들을 충분히 빠르게 처리할 수 있겠는가?

첫 줄에 세 정수 $n$, $m$, $q$ ($1 \le n, m, q \le 10^5$)가 주어진다.

이어지는 $m$개의 줄에는 각각 두 정수 $x$, $y$가 주어지며, 이는 그래프의 간선 $(x, y)$를 나타낸다 ($1 \le x, y \le n$). 입력 그래프가 DAG임이 보장된다.

이어지는 $q$개의 줄에는 다음 중 하나의 형식으로 연산이 주어진다.

• 1 u x: 첫 번째 종류의 연산이다.
• 2 u x: 두 번째 종류의 연산이다.
• 3 u: 세 번째 종류의 연산이다.

모든 매개변수는 $1 \le u \le n$, $0 \le x \le 10^9$을 만족한다.

세 번째 종류의 연산마다 한 줄에 정수 하나를 출력한다. 그 정수는 현재의 $\mathit{val}_u$ 값이다.