You are given a Directed Acyclic Graph (DAG) with $n$ vertices and $m$ edges. Each vertex $v$ has an integer, $a_v$, associated with it and the initial value of $a_v$ is $0$ for all vertices. You must perform $\textit{q}$ queries on the DAG, where each query is one of the following types:

1 u x: Set $a_v$ to $\boldsymbol{x}$ for all $v$ such that there is a path in the DAG from $\mbox{u}$ to $v$.
2 u x: Set $a_v$ to $\boldsymbol{x}$ for all $v$ such that there is a path from $\mbox{u}$ to $v$ and $a_v>x$.
3 u: Print the value of $a_{u}$ on a new line.

Input Format

The first line contains three space-separated integers describing the respective values of $n$ (the number of vertices in the DAG), $m$ (the number of edges in the DAG), and $\textit{q}$ (the number of queries to perform). 

Each of the $m$ subsequent lines contains two space-separated integers describing the respective values of $\mbox{u}$ and $v$ (where $1\leq u,v\leq n$, $u\neq v$) denoting a directed edge from vertex $\mbox{u}$ to vertex $v$ in the graph. 

Each of the $\textit{q}$ subsequent lines contains a query in one of the three formats described above.

Constraints

$2\leq n\leq10^5$
$1\leq m,q\leq10^5$
$0\leq x\leq10^9$
$0\leq a_v\leq10^9$
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 $3$ (i.e., 3 u), print the value of $a_{u}$ 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 $1$ and type $2$ queries:

Source: hackerrank | Difficulty: HARD
Tags: Graph algorithms


Solutions:
from functools import reduce

def readVec():
	return tuple((int(it) for it in input().split()))
(n, m, q) = readVec()
vertexes = [0 for it in range(n + 1)]
edges = {it: set() for it in range(n + 1)}
for it in range(m):
	(a, b) = readVec()
	edges[a] |= {b}

def memoize(f):
	cache = {}

	def ret(n):
		if n not in cache:
			cache[n] = f(n)
		return cache[n]
	return ret

@memoize
def reachable(n):
	return reduce(lambda x, y: x | y, (reachable(it) for it in edges[n]), {n})
for it in range(q):
	query = readVec()
	if query[0] == 1:
		for it in reachable(query[1]):
			vertexes[it] = query[2]
	elif query[0] == 2:
		for it in reachable(query[1]):
			vertexes[it] = min(vertexes[it], query[2])
	elif query[0] == 3:
		print(vertexes[query[1]])


import sys

class Node(object):

	def __init__(self):
		self.a = 0
		self.outs = set()
		self.evaluated = False

	def rec(self):
		if not self.evaluated:
			nouts = set()
			for v in self.outs:
				nouts |= v.rec()
			self.outs |= nouts
			self.evaluated = True
		return self.outs

	def set1(self, x):
		self.rec()
		self.a = x
		for v in self.outs:
			v.a = x

	def set2(self, x):
		self.rec()
		self.a = min(x, self.a)
		for v in self.outs:
			v.a = min(x, v.a)

	def get(self):
		return self.a

	def connect(self, v):
		self.outs.add(v)
lines = sys.stdin.readlines()
(n, m, q) = (int(x) for x in lines[0].split())
graph = [Node() for _ in range(n + 1)]
for l in lines[1:1 + m]:
	(u, v) = (int(x) for x in l.split())
	graph[u].connect(graph[v])
for l in lines[1 + m:1 + m + q]:
	if l[0] == '1':
		(_, u, x) = (int(x) for x in l.split())
		graph[u].set1(x)
	elif l[0] == '2':
		(_, u, x) = (int(x) for x in l.split())
		graph[u].set2(x)
	elif l[0] == '3':
		(_, u) = (int(x) for x in l.split())
		print(graph[u].get())


def bfs(dic, adj, avval, svertex, value, code):
	if svertex in dic:
		if code == 1:
			for i in dic[svertex]:
				avval[i] = value
		if code == 2:
			for i in dic[svertex]:
				if avval[i] > value:
					avval[i] = value
	else:
		frontier = [svertex]
		dic[svertex] = [svertex]
		visited = {svertex: 1}
		if code == 1:
			avval[svertex] = value
		elif code == 2:
			if avval[svertex] > value:
				avval[svertex] = value
		while len(frontier) > 0:
			nl = []
			for a in frontier:
				for b in adj[a]:
					if b not in visited:
						dic[svertex].append(b)
						if code == 1:
							avval[b] = value
						if code == 2:
							if value < avval[b]:
								avval[b] = value
						visited[b] = 1
						nl.append(b)
			frontier = nl
(n, m, q) = map(int, input().split())
avval = [0 for a in range(n)]
adj = [[] for a in range(n)]
dic = {}
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	adj[u].append(v)
for i in range(q):
	temp = [int(a) for a in input().split()]
	if temp[0] == 1:
		bfs(dic, adj, avval, temp[1] - 1, temp[2], 1)
	elif temp[0] == 2:
		bfs(dic, adj, avval, temp[1] - 1, temp[2], 2)
	elif temp[0] == 3:
		print(avval[temp[1] - 1])


def dfs(start):
	visited[start] = True
	connections[start].add(start)
	for neighbour in G[start]:
		if not visited[neighbour]:
			dfs(neighbour)
		connections[start] = connections[start].union(connections[neighbour])
(n, m, q) = [int(x) for x in input().split()]
global G, connections, visited
G = [set() for _ in range(n + 1)]
for _ in range(m):
	(u, v) = [int(x) for x in input().split()]
	G[u].add(v)
visited = [False for _ in range(n + 1)]
connections = [set() for _ in range(n + 1)]
for i in range(1, len(visited)):
	if not visited[i]:
		dfs(i)
avals = [0 for _ in range(n + 1)]
for _ in range(q):
	s = input().rstrip()
	if s[0] == '1':
		(__, u, x) = [int(x) for x in s.split()]
		for connection in connections[u]:
			avals[connection] = x
	elif s[0] == '2':
		(__, u, x) = [int(x) for x in s.split()]
		for connection in connections[u]:
			avals[connection] = min(avals[connection], x)
	elif s[0] == '3':
		(__, u) = [int(x) for x in s.split()]
		print(avals[u])


from functools import lru_cache

@lru_cache(maxsize=None)
def all_children(node):
	children = {node}
	for child in graph[node]['children']:
		children |= all_children(child)
	return children
(n, m, q) = map(int, input().split())
graph = {}
for i in range(n):
	graph[i + 1] = {'value': 0, 'children': set()}
for i in range(m):
	(u, v) = map(int, input().split())
	graph[u]['children'].add(v)
queries = [list(map(int, input().split())) for i in range(q)]
for query in queries:
	command = query[0]
	node = query[1]
	if command == 1:
		value = query[2]
		for child in all_children(node):
			graph[child]['value'] = value
	elif command == 2:
		value = query[2]
		for child in all_children(node):
			graph[child]['value'] = min(value, graph[child]['value'])
	elif command == 3:
		print(graph[node]['value'])


from collections import deque, defaultdict, OrderedDict
(n, m, q) = tuple(map(int, input().strip().split(' ')))
r = defaultdict(int)
cache = defaultdict(set)
for i in range(1, n + 1):
	r[i] = 0

class DAG(object):

	def __init__(self):
		self.graph = OrderedDict()
		self.order = None

	def add_node(self, node_name, graph=None):
		if not graph:
			graph = self.graph
		graph[node_name] = set()

	def add_edge(self, ind_node, dep_node, graph=None):
		if not graph:
			graph = self.graph
		graph[ind_node].add(dep_node)

	def all_downstreams(self, node, graph=None):
		if graph is None:
			graph = self.graph
		if self.order is None:
			self.order = self.topological_sort(graph=graph)
		nodes = [node]
		nodes_seen = set()
		i = 0
		while i < len(nodes):
			downstreams = self.graph[nodes[i]]
			for downstream_node in downstreams:
				if downstream_node not in nodes_seen:
					nodes_seen.add(downstream_node)
					nodes.append(downstream_node)
			i += 1
		return self.order & nodes_seen

	def topological_sort(self, graph=None):
		if graph is None:
			graph = self.graph
		in_degree = {u: 0 for u in graph}
		for u in graph:
			for v in graph[u]:
				in_degree[v] += 1
		Q = deque()
		for u in in_degree:
			if in_degree[u] == 0:
				Q.appendleft(u)
		L = set()
		while Q:
			u = Q.pop()
			L.add(u)
			for v in graph[u]:
				in_degree[v] -= 1
				if in_degree[v] == 0:
					Q.appendleft(v)
		if len(L) == len(graph):
			return L
		else:
			return set()
d = DAG()
for i in range(n + 1):
	d.add_node(i + 1)
for i in range(m):
	(s, de) = tuple(map(int, input().strip().split(' ')))
	d.add_edge(s, de)
for i in range(n + 1):
	cache[i + 1] = set([i + 1]) | set(d.all_downstreams(i + 1))
for i in range(q):
	s = input().strip().split(' ')
	a = int(s[0])
	b = int(s[1])
	c = None
	if len(s) > 2:
		c = int(s[2])
	if a == 1:
		for n in cache[b]:
			r[n] = c
	elif a == 2:
		for n in cache[b]:
			if r[n] > c:
				r[n] = c
	else:
		print(r[b])


import sys

def get_graph(n, m):
	g = {i: None for i in range(1, n + 1)}
	for node in g:
		g[node] = [[], 0]
	for _ in range(m):
		(a, b) = map(int, input().split())
		g[a][0].append(b)
	return g

def get_subgraph(g, a):
	cg = []
	touched_nodes = set([a])
	candidate_nodes = set([a])
	while candidate_nodes:
		n = candidate_nodes.pop()
		cg.append(n)
		for b in g[n][0]:
			if b not in touched_nodes:
				candidate_nodes.add(b)
			touched_nodes.add(b)
	return cg

def traverse(g, sg, op, x):
	for n in sg:
		if op == 1:
			g[n][1] = x
		elif op == 2 and g[n][1] > x:
			g[n][1] = x
(n, m, q) = map(int, input().split())
g = get_graph(n, m)
subgraphs = {a: get_subgraph(g, a) for a in g}
for _ in range(q):
	s = input()
	mp = map(int, s.split())
	if s[0] == '3':
		(op, u) = mp
		print(g[u][1])
	else:
		(op, u, x) = mp
		traverse(g, subgraphs[u], op, x)


from collections import defaultdict, deque, OrderedDict

def run_commands(g, v, commands):
	for (node, value) in commands.items():
		if node < 0:
			node = -node
			if v[node] > value:
				v[node] = value
			for child in g[node]:
				if v[child] > value:
					v[child] = value
		else:
			v[node] = value
			for child in g[node]:
				v[child] = value
(n, m, q) = [int(x) for x in input().strip().split(' ')]
values = [0] * (n + 1)
done = [False] * (n + 1)
graph = {k: set() for k in range(1, n + 1)}
for _ in range(m):
	(u, v) = [int(x) for x in input().strip().split(' ')]
	graph[u].add(v)

def update_children(c, d, start):
	que = deque(((start, child) for child in c[start]))
	while que:
		(parent, node) = que[0]
		if d[node]:
			c[parent].update(c[node])
			que.popleft()
		else:
			d[node] = True
			que.extendleft(((node, child) for child in c[node]))
for (node, p_set) in graph.items():
	if done[node]:
		continue
	update_children(graph, done, node)
	done[node] = True
del done
set_commands = OrderedDict()
for _ in range(q):
	query = [int(x) for x in input().strip().split(' ')]
	if query[0] == 3:
		run_commands(graph, values, set_commands)
		set_commands.clear()
		print(values[query[1]])
	elif query[0] == 1:
		(node, value) = query[1:]
		set_commands[node] = value
		set_commands.move_to_end(node)
		set_commands.pop(-node, None)
	else:
		(node, value) = query[1:]
		set_commands[-node] = value


(N, M, Q) = [int(n) for n in input().split()]
G = dict()
for _ in range(M):
	(u, v) = [int(n) for n in input().split()]
	if u in G:
		G[u].append(v)
	else:
		G[u] = [v]
val = [0] * (N + 1)
mem = dict()

def nodesInPath(root):
	if root in mem:
		return mem[root]
	inPath = {root}
	if root in G:
		for node in G[root]:
			inPath |= nodesInPath(node)
	mem[root] = inPath
	return inPath
for _ in range(Q):
	query = [int(n) for n in input().split()]
	if query[0] == 1:
		for node in nodesInPath(query[1]):
			val[node] = query[2]
	elif query[0] == 2:
		for node in nodesInPath(query[1]):
			val[node] = min(query[2], val[node])
	else:
		print(val[query[1]])


(n, m, q) = list(map(lambda x: int(x), input().split()))
(G, A, Paths) = ({}, {}, {})
for u in range(1, n + 1):
	G[u] = []
	A[u] = 0
	Paths[u] = set()
for j in range(1, m + 1):
	(u, v) = list(map(lambda x: int(x), input().split()))
	G[u].append(v)
	Paths[u].add(v)

def dfs(u, Paths, S=None):
	if S is None:
		S = set()
	if u in S:
		return (Paths, S)
	S.add(u)
	for v in G[u]:
		if v in S:
			Paths[u] = Paths[u].union(Paths[v])
			continue
		(Paths, S) = dfs(v, Paths, S)
		Paths[u] = Paths[u].union(Paths[v])
	return (Paths, S)
S = set()
for u in range(1, n + 1):
	(Paths, S) = dfs(u, Paths, S)
for _ in range(1, q + 1):
	query = list(map(lambda x: int(x), input().split()))
	if query[0] == 1:
		(_, u, x) = query
		A[u] = x
		for v in Paths[u]:
			A[v] = x
	elif query[0] == 2:
		(_, u, x) = query
		if A[u] > x:
			A[u] = x
		for v in Paths[u]:
			if A[v] > x:
				A[v] = x
	elif query[0] == 3:
		(_, u) = query
		print(A[u])


import sys

def connect(u, v, G):
	u -= 1
	G[u].append(v)

def dfs(G, s, S):
	if S is None:
		S = set()
	Stack = []
	Stack.append(s)
	while Stack:
		s = Stack[len(Stack) - 1]
		S.add(s)
		flag = True
		next = None
		for u in G[s - 1]:
			if u not in S:
				flag = False
				next = u
				continue
		if flag:
			Stack.pop()
		else:
			Stack.append(next)
stdinput = sys.stdin
parsedLine = stdinput.readline().split()
n = int(parsedLine[0])
m = int(parsedLine[1])
q = int(parsedLine[2])
avalues = [0] * n
adjacencyList = [[] for i in range(n)]
paths = {}
for i in range(m):
	parsedLine = stdinput.readline().split()
	connect(int(parsedLine[0]), int(parsedLine[1]), adjacencyList)
for u in range(1, n + 1):
	myset = set()
	dfs(adjacencyList, u, myset)
	paths[u] = list(myset)
for i in range(q):
	parsedLine = stdinput.readline().split()
	if int(parsedLine[0]) == 1:
		u = int(parsedLine[1])
		x = int(parsedLine[2])
		for n in paths[u]:
			avalues[n - 1] = x
	elif int(parsedLine[0]) == 2:
		u = int(parsedLine[1])
		x = int(parsedLine[2])
		for n in paths[u]:
			if avalues[n - 1] > x:
				avalues[n - 1] = x
	elif int(parsedLine[0]) == 3:
		u = int(parsedLine[1])
		print(avalues[u - 1])


from collections import namedtuple, deque
Node = namedtuple('Node', ['value', 'adj_vertices'])

def init_graph(vertices, edges):
	graph = {i: [0, set()] for i in range(1, vertices + 1)}
	for _ in range(edges):
		edge = input()
		(from_node, to_node) = map(int, edge.split(' '))
		graph[from_node][1].add(to_node)
	return graph

def dfs(graph, start):
	(visited, queue) = (set(), deque([start]))
	while queue:
		vertex = queue.pop()
		if vertex not in visited:
			visited.add(vertex)
			queue.extend(graph[vertex][1] - visited)
	return visited

def execute_queries(graph, queries):
	subgraph_nodes = {vertex: dfs(graph, vertex) for vertex in graph}
	for _ in range(queries):
		query = input()
		query = [int(n) for n in query.split(' ')]
		(q_type, vertex) = query[:2]
		if q_type == 3:
			print(graph[vertex][0])
			continue
		new_value = query[2]
		for node in subgraph_nodes[vertex]:
			if q_type == 1 or (q_type == 2 and graph[node][0] > new_value):
				graph[node][0] = new_value

def get_graph_config():
	graph_conf = input()
	(v_count, e_count, q_count) = map(int, graph_conf.split(' '))
	return (v_count, e_count, q_count)
(vertices_count, edges_count, queries_count) = get_graph_config()
dag_graph = init_graph(vertices_count, edges_count)
execute_queries(dag_graph, queries_count)


from functools import reduce

def readVec():
	return tuple((int(it) for it in input().split()))
(n, m, q) = readVec()
vertexes = [0 for it in range(n + 1)]
edges = {it: set() for it in range(n + 1)}
for it in range(m):
	(a, b) = readVec()
	edges[a] |= {b}

def memoize(f):
	cache = {}

	def ret(n):
		if n not in cache:
			cache[n] = f(n)
		return cache[n]
	return ret

@memoize
def reachable(n):
	return reduce(lambda x, y: x | y, (reachable(it) for it in edges[n]), {n})
for it in range(q):
	query = readVec()
	if query[0] == 1:
		for it in reachable(query[1]):
			vertexes[it] = query[2]
	elif query[0] == 2:
		for it in reachable(query[1]):
			vertexes[it] = min(vertexes[it], query[2])
	elif query[0] == 3:
		print(vertexes[query[1]])


p = input()
parts = p.split(' ')
(nodes, edges, queries) = [int(x) for x in parts]
adj = {i: set() for i in range(1, nodes + 1)}
for i in range(edges):
	p = input()
	newP = p.split(' ')
	(fro, dest) = [int(x) for x in newP]
	adj[fro].add(dest)
val = [0] * (nodes + 1)
visited = set()

def dfs(base, nd):
	if nd in visited:
		return
	adj[base].add(nd)
	visited.add(nd)
	for nex in adj[nd]:
		if nex not in visited:
			dfs(base, nex)
	return
for i in range(1, nodes + 1):
	visited.clear()
	s = adj[i].copy()
	for j in s:
		dfs(i, j)
for i in range(queries):
	p = input()
	newP = p.split(' ')
	cmd = [int(x) for x in newP]
	if cmd[0] == 1:
		val[cmd[1]] = cmd[2]
		for canV in adj[cmd[1]]:
			val[canV] = cmd[2]
	elif cmd[0] == 2:
		if val[cmd[1]] > cmd[2]:
			val[cmd[1]] = cmd[2]
		for canV in adj[cmd[1]]:
			if val[canV] > cmd[2]:
				val[canV] = cmd[2]
	else:
		print(val[cmd[1]])


from functools import reduce

def readVec():
	return tuple((int(it) for it in input().split()))
(n, m, q) = readVec()
vertexes = [0 for it in range(n + 1)]
edges = {it: set() for it in range(n + 1)}
for it in range(m):
	(a, b) = readVec()
	edges[a] |= {b}

def memoize(f):
	cache = {}

	def ret(n):
		if n not in cache:
			cache[n] = f(n)
		return cache[n]
	return ret

@memoize
def reachable(n):
	return reduce(lambda x, y: x | y, (reachable(it) for it in edges[n]), {n})
for it in range(q):
	query = readVec()
	if query[0] == 1:
		for it in reachable(query[1]):
			vertexes[it] = query[2]
	elif query[0] == 2:
		for it in reachable(query[1]):
			vertexes[it] = min(vertexes[it], query[2])
	elif query[0] == 3:
		print(vertexes[query[1]])