You are given a Directed Acyclic Graph (DAG) with vertices and edges. Each vertex has an integer, , associated with it and the initial value of is for all vertices. You must perform queries on the DAG, where each query is one of the following types:
1 u x: Set to for all such that there is a path in the DAG from to .2 u x: Set to for all such that there is a path from to and .3 u: Print the value of on a new line.
Input Format
The first line contains three space-separated integers describing the respective values of (the number of vertices in the DAG), (the number of edges in the DAG), and (the number of queries to perform).
Each of the subsequent lines contains two space-separated integers describing the respective values of and (where , ) denoting a directed edge from vertex to vertex in the graph.
Each of the subsequent lines contains a query in one of the three formats described above.
Constraints
- It's guaranteed that the graph is acyclic, but there may be more than one edge connecting two nodes.
Output Format
For each query of type (i.e., 3 u), print the value of on a new line.
Sample Input 0
6 5 18
1 2
1 3
3 4
2 4
5 6
1 1 3
3 1
3 2
3 3
3 4
1 2 2
3 1
3 2
3 3
3 4
2 6 7
3 5
3 6
2 1 3
3 1
3 2
3 3
3 4
Sample Output 0
3
3
3
3
3
2
3
2
0
0
3
2
3
2
Explanation 0
The diagram below depicts the changes to the graph after all type and type queries:
