in a interview the interviewer will ask the question for the porblem
"""

Locking The Tree of Space
You have a world map represented as an M-Ary tree (sample tree below)

asterisk_green.svgIn graph theory, an m-ary tree (for nonnegative integers m) (also known as n-ary, k-ary or k-way tree) is an arborescence (or an ordered tree) in which each node has no more than m children. A binary tree is the special case where m = 2, and a ternary tree is another case with m = 3 that limits its children to three.

asterisk_green.svgIn graph theory, an arborescence is a directed graph in which, for a vertex u (called the root) and any other vertex v, there is exactly one directed path from u to v. A graph is a collection of vertices (also known as nodes) and edges that connect these vertices. A tree is a special type of graph that is connected and acyclic, meaning that there are no cycles in the graph. In a tree, there is a unique path between any two vertices, and there is a single vertex called the root that is used as the starting point for traversing the tree.

Sample Tree

You need to define three operations on it:


1. lock(X, uid)
2. unlock(X, uid)
3. upgradeLock(X, uid)
where X the name of a node in the tree (that would be unique) and uid is the user who is performing the operation.
Input format: x is country name (string) and uid is user number (number).

Here are the definitions for the operations:

lock(x, uid)
Lock takes an exclusive access on the subtree rooted at X. It is formally defined like this: Once lock(x, uid) succeeds, then:
lock(A, anyUserid) should fail (returns false), where A is a descendent of X,

lock(B, anyUserld) should fail (returns false), where X is a descendent of B,

Lock operation cannot be performed on a node which is already locked i.e. lock(x, anyUserld) should fail (returns false).


asterisk_green.svgExclusive access means that only one user can lock a node and its descendants at a time, and no other user can lock any node that is related to the locked node by ancestry or descent. This ensures that there is no conflict or interference between different users who want to perform operations on the tree.
unlock(X, uid)
Unlock reverts what was done by the lock operation. It can only be called on same node on which user uid had called a Lock on before. Returns true if it is successful.

upgradeLock(x, uid)
It helps the user uid upgrade their lock to an ancestor node. It is only possible if the node X already has locked descendants and all of them are only locked by the same user uid. Upgrade should fail if there is any node which is descendant of X that is locked by a different user. Successful Upgrade will 'lock' the node. upgradeLock call shouldn't violate the consistency model that Lock/Unlock function requires.

Notes

The number of nodes in the tree N is very large. So, optimize the time complexity for the above algorithms.
The below section contains the input format.
The first line contains the number of Nodes in the tree (N).
The second line contains number of children per node (value m in m-ary Tree).
The third line contains number of queries (Q).
Next N lines contains the NodeName (string) in the m-Ary Tree.
Next Q lines contains queries which are in format: 
Operation Type NodeName Userld
Operation Type 1 for lock
2 for unlock
3 for upgradeLock
NodeName - Name of any node (unique) in m-Ary Tree.
Userld - Integer value representing a unique user.
Example input


7
2
3
World
Asia
Africa
China
India
South Africa
Egypt
1 China 9
2 India 9
3 Asia 9
With the above input you represent a 2-ary tree with 7 nodes as follows:


                 World
            /             \
        Asia               Africa
      /      \          /         \
China    India    South Africa   Egypt
Additional Notes

Here 1 China 3 indicates the following 'Operation Type NodeName Userld'.
The tree is always fully balanced.
Constraints on the inputs are as follows:
1 < N < 5 * 10^5
1 < m < 30
1 < Q <5 * 10^5
1 < length of NodeName < 20
Optimize the time complexity:
Lock - O(logmN)
Unlock - O(logmN)
UpgradeLock - O(numberOfLockedNodes * logmN)
Lock operation on already locked node should fail.
Once Upgrade lock(X, uid) succeeds on X. It is equivalent to X being locked by uid. So, Lock(A/B, anyuser) should fail as per the definition of Lock and Unlock(X, uid) should also work.
Upgrade lock operation on a node having no locked descendants should fail and upgrade lock on already locked node should also fail.
Example input


7
2
5
World
Asia
Africa
China
India
SouthAfrica
Egypt
1 China 9
1 India 9
3 Asia 9
2 India 9
2 Asia 9
Example input


true
true
true
false
true
Query 1: 1 China 9 ⇒ This operation is success as initially China is unlocked.

Query 2: 1 India 9 ⇒ This should be success as none of ancestors and descendants of India are locked.

Query 3: 3 Asia 9 ⇒ This also should be success as upgrade operation is done by same user who has locked descendants.

Query 4: 2 India 9 ⇒ This should fail as the India is now not locked

Query 5: 2 Asia 9 ⇒ This should be success as Asia was earlier (refer Query 3) locked by user 9.
"""
Let’s say you are running the lock/unlock in a multi core machine. Now you want to let multiple threads to run lock() As we saw in part A, locking a node has multiple validations inside. Will doing lock on two nodes cause a race condition. If yes, how will you solve it. In short,
how do make the lock() function thread safe? - Multiple threads running it simultaneously shouldn’t not affect the correctness. -Try to make the critical sections more granular.
ie. don’t create any big atomic/synchronised blocks that will make parallelism suffer.

"""
my code is
"""
import sys

Increase recursion limit
sys.setrecursionlimit(1 << 25)

class Node:
def init(self, val):
self.val = val
self.uid = None # User ID of the user who locked this node
self.parent = None # Parent node
self.child = [] # List of child nodes
self.isLocked = False # Indicates if the node is currently locked
self.lockedDescendantCount = 0 # Number of locked descendants

class Tree:
def init(self, m, n, name_list):
self.node_list = []
self.node_map = {}


    for name in name_list:
        node = Node(name)
        self.node_list.append(node)
        self.node_map[name] = node

    # Build the tree
    for i in range(n):
        for j in range(m):
            child_index = m * i + j + 1
            if child_index < n:
                self.node_list[i].child.append(self.node_list[child_index])
                self.node_list[child_index].parent = self.node_list[i]

    self.root = self.node_list[0]

def lock(self, node, uid):
    if node.isLocked:
        return False

    if self.isAncestorLocked(node):
        return False

    if node.lockedDescendantCount > 0:
        return False

    # Lock the node
    node.isLocked = True
    node.uid = uid

    # Update the lockedDescendantCount for ancestors
    parent = node.parent
    while parent:
        parent.lockedDescendantCount += 1
        parent = parent.parent

    return True

def unlock(self, node, uid):
    if not node.isLocked or node.uid != uid:
        return False

    # Unlock the node
    node.isLocked = False
    node.uid = None

    # Update the lockedDescendantCount for ancestors
    parent = node.parent
    while parent:
        parent.lockedDescendantCount -= 1
        parent = parent.parent

    return True

def upgrade(self, node, uid):
    if node.isLocked:
        return False

    if self.isAncestorLocked(node):
        return False

    if node.lockedDescendantCount == 0:
        return False

    locked_descendants = []

    # Collect all locked descendants
    if not self.collectLockedDescendants(node, uid, locked_descendants):
        return False

    # Unlock all locked descendants
    for descendant in locked_descendants:
        descendant.isLocked = False
        descendant.uid = None

        # Update the lockedDescendantCount for ancestors
        parent = descendant.parent
        while parent:
            parent.lockedDescendantCount -= 1
            parent = parent.parent

    # Lock the current node
    node.isLocked = True
    node.uid = uid

    # Update the lockedDescendantCount for ancestors
    parent = node.parent
    while parent:
        parent.lockedDescendantCount += 1
        parent = parent.parent

    return True

def isAncestorLocked(self, node):
    curr = node.parent
    while curr:
        if curr.isLocked:
            return True
        curr = curr.parent
    return False

def collectLockedDescendants(self, node, uid, locked_nodes):
    if node.isLocked:
        if node.uid == uid:
            locked_nodes.append(node)
        else:
            return False  # Locked by different uid

    for child_node in node.child:
        if not self.collectLockedDescendants(child_node, uid, locked_nodes):
            return False
    return True

def process_queries(self, queries):
    results = []
    for query in queries:
        operation, node_name, uid = query.strip().split()
        uid = int(uid)
        node = self.node_map[node_name]
        if operation == "1":
            result = self.lock(node, uid)
        elif operation == "2":
            result = self.unlock(node, uid)
        elif operation == "3":
            result = self.upgrade(node, uid)
        else:
            result = False  # Invalid operation
        results.append('true' if result else 'false')
    return results
def main():
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
q = int(sys.stdin.readline())
name_list = [sys.stdin.readline().strip() for _ in range(n)]
queries = [sys.stdin.readline().strip() for _ in range(q)]
tree = Tree(m, n, name_list)
results = tree.process_queries(queries)
for res in results:
print(res)

main()

"""
how can this be thread safe only. for the LOCK method


Let’s say you are running the lock/unlock in a multi core machine. Now you want to let multiple threads to run lock() As we saw in part A, locking a node has multiple validations inside. Will doing lock on two nodes cause a race condition. If yes, how will you solve it. In short,
how do make the lock() function thread safe? - Multiple threads running it simultaneously shouldn’t not affect the correctness. -Try to make the critical sections more granular.
ie. don’t create any big atomic/synchronised blocks that will make parallelism suffer.
Interviewer switched back to the previous question and asked, Implement thread safe concurrent lock method without using any atomic method, mutex, semaphores, synchronized keywork