We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. DAG Queries

DAG Queries

Problem
Submissions
Leaderboard
Discussions
Editorial

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. 1 u x: Set to for all such that there is a path in the DAG from to .
  2. 2 u x: Set to for all such that there is a path from to and .
  3. 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:

image

Author

zemen

Difficulty

Expert

Max Score

80

Submitted By

1261

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy