City Construction Solution times out for large input
It was a tough one but I managed to solve it and pass all the test cases. Below are main points.

Build a full directed graph first

Save the queries because there can be up to 100,000 of them and it's more efficient to build a full graph first and then run all the queries on it.

Find all strongly connected components

Find all strongly connected components in the graph and then build a reachability map based on them. It has a lower space complexity since each strong component can be represented by a single node and so we don't need to have a reachability set for each node but only for its representative.

Use DFS for finding reachability sets

Modify a DFS so that after running it each connected component contains representatives (so-called low-link nodes) from other connected components that are reachable. But then, if a low link node is reachable so is any node from its connected component.

Use memory efficiently for storing strong components

Create an array of (n + 1) integer values, where n - the number of nodes in the graph. Index identifies a node in the graph and a value - all connected components (low link node) reachable from it. Value can have up to n + 1 binary digits (if all nodes are reachable from the current one).

Increase recursion limit 

As the number of nodes can reach 50000 so the recursion call stack must be set to this value.

Solution Code

from collections import defaultdict, deque
import sys

sys.setrecursionlimit(50001)

n, m = map(int, input().split())
adjacentNodes = defaultdict(set)
for _ in range(m):
    u, v = map(int, input().split())
    adjacentNodes[u].add(v)

q = int(input())
# read all queries first
queries = []
for i in range(q):
    c, x, d = map(int, input().split())
    if c == 1:
        n += 1
        y = n
        if d == 0:
            adjacentNodes[x].add(y)
        else:
            adjacentNodes[y].add(x)
    else:
        y = d
        queries.append((x, y))

# each node with number i corresponds to 2^i
nodeDpPosition = {i: (1 &lt;&lt; i) for i in range(n + 1)}
# Implementation using the Tarjan algorithm
# https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
def findAllConnectedComponents(edges):
    connectedComponents = [0 for _ in range(n + 1)]
    index = {'value' : 0}
    # map node to its connected component low link node
    connectedComponentLink = {}

    nodeStack = deque()
    indices = [-1] * (n + 1)
    lowLinks = [0] * (n + 1)
    onStack = [False] * (n + 1)

    def connectedComponent(node):
        indices[node] = index['value']
        lowLinks[node] = index['value']
        index['value'] += 1
        nodeStack.append(node)
        onStack[node] = True

        for adjacentNode in edges[node]:
            if indices[adjacentNode] &lt; 0:
                connectedComponent(adjacentNode)
                lowLinks[node] = min(lowLinks[node], lowLinks[adjacentNode])
            elif onStack[adjacentNode]:
                # we have reached the previously visited node or come back in the call stack
                lowLinks[node] = min(lowLinks[node], indices[adjacentNode])

        if lowLinks[node] == indices[node]:
            while nodeStack:
                current = nodeStack.pop()
                connectedComponentLink[current] = node
                onStack[current] = False
                connectedComponents[node] |= nodeDpPosition[current]

                if current == node:
                    break

    for i in range(1, n + 1):
        if indices[i] &lt; 0:
            connectedComponent(i)

    return (connectedComponents, connectedComponentLink)

connectedComponents, connectedComponentLink = findAllConnectedComponents(adjacentNodes)

def advancedDfs(node):
    lowLinkNode = connectedComponentLink[node]

    neighbours = adjacentNodes.get(node)
    if neighbours is not None:
        for neighbour in neighbours:
            lowLinkNeighbourNode = connectedComponentLink[neighbour]
            if (connectedComponents[lowLinkNode] &amp; nodeDpPosition[lowLinkNeighbourNode]) == 0:
                connectedComponents[lowLinkNode] |= nodeDpPosition[lowLinkNeighbourNode]
                advancedDfs(lowLinkNeighbourNode)

            connectedComponents[lowLinkNode] |= connectedComponents[lowLinkNeighbourNode]

for i in range(1, n + 1):
    advancedDfs(i)

for query in queries:
     x, y = query
     lowLinkXNode = connectedComponentLink[x]
     lowLinkYNode = connectedComponentLink[y]
     if connectedComponents[lowLinkXNode] &amp; nodeDpPosition[lowLinkYNode]:
         print ("Yes")
     else:
         print ("No")