시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 0 | 0 | 0 | 0.000% |
Recently, Rikka showed great interest in the data structures for directed acyclic graphs (DAGs). She dreams that extending classic tree-based algorithms like "weighted-chain decomposition" to their counterparts based on DAGs will be perfectly cooooool!
Now, she came up with a simple problem, and she would like to invite you to solve this problem with her.
You are given an $n$-node $m$-edge DAG $G$. Each node $u$ has a non-negative integer value $\mathit{val}_u$. All values are set to $0$ initially.
Rikka wants to perform $q$ operations of three types described below:
Can you perform all these operations fast enough?
A node $v$ is said to be reachable from $u$ if there is a path starting in $u$ and ending in $v$. A path is a node sequence $p_1, p_2, \ldots, p_k$ satisfying $(p_i, p_{i + 1}) \in G$ for each $i = 1, 2, \ldots, k - 1$.
The first line of input contains three integers $n$, $m$, $q$ ($1 \le n, m, q \le 10^5$).
Then $m$ lines follow. Each of them contains two integers $x$ and $y$, representing a directed edge $(x, y)$ in the graph ($1 \le x, y \le n$). The input graph is guaranteed to be a DAG.
Then $q$ lines follow. Each of them contains two or three integers in one of the following three formats:
1 u x
" indicating the first type of operation;2 u x
" indicating the second type of operation;3 u
" indicating the third type of operation.All parameters in the operations above satisfy $1 \le u \le n$ and $0 \le x \le 10^9$.
For each operation of the third type, print a single line containing an integer: the current value of $\mathit{val}_u$.
4 4 7 1 2 1 3 3 4 2 4 1 1 5 1 2 1 3 3 3 4 2 1 3 3 2 3 3
5 1 1 3