Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


class LowestCommonAncestor:
    def __init__(self, graph, root):
        self.graph = graph
        self.root = root
        self._dfs()

    def _dfs(self):
        n = self.graph.v
        visited = [False] * n
        parent = [None] * n
        post_order = [0] * n

        stack = [self.root]
        i = 0
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                stack.append(v)
                for e in self.graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        parent[w] = v
                        stack.append(w)
            else:
                post_order[v] = i
                i += 1

        self.post_order = post_order
        self.parent = parent

    def find(self, v, w):
        ps = self.parent
        pos = self.post_order
        i = pos[v]
        j = pos[w]
        if i > j:
            i, j = j, i
            v, w = w, v

        while i < j and v != self.root:
            v = ps[v]
            i = pos[v]
        return v


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    lca = LowestCommonAncestor(g, 0)
    q = int(input())
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        print(lca.find(v, w))


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor


class UnionFind:
    def __init__(self, n):
        self.nodes = [i for i in range(n)]
        self.sizes = [1 for _ in range(n)]

    def union(self, p, q):
        rp = self.root(p)
        rq = self.root(q)
        if self.sizes[rp] > self.sizes[rq]:
            self.nodes[rq] = rp
            self.sizes[rp] += self.sizes[rq]
        else:
            self.nodes[rp] = rq
            self.sizes[rq] += self.sizes[rp]

    def connected(self, p, q):
        return self.root(p) == self.root(q)

    def root(self, p):
        while p != self.nodes[p]:
            self.nodes[p] = self.nodes[self.nodes[p]]
            p = self.nodes[p]

        return p


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class WeightedEdge(Edge):
    __slots__ = ('v', 'w', 'weight')

    def __init__(self, v, w, weight):
        super().__init__(v, w)
        self.weight = weight


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def lca(graph, root, queries):
    index = [set() for _ in range(graph.v)]
    for v, w in queries:
        index[v].add((v, w))

    visited = [False] * graph.v
    stored = [False] * graph.v
    parents = [None] * graph.v
    uf = UnionFind(graph.v)
    res = {}
    stack = [root]
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            stack.append(v)
            for e in graph.adj(v):
                w = e.other(v)
                if not visited[w]:
                    stack.append(w)
                    parents[w] = v
        else:
            stored[v] = True
            p = parents[v]
            rest = set()
            for i, j in index[v]:
                if stored[i] and stored[j]:
                    if uf.connected(i, j) and (i, j) not in res:
                        res[(i, j)] = v
                    else:
                        rest.add((i, j))
                else:
                    index[j].add((i, j))
            index[v] = None
            if p is not None:
                uf.union(p, v)
                index[p].update(rest)

    return res


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    q = int(input())
    qs = []
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        qs.append((v, w))

    res = lca(g, 0, qs)
    for v, w in qs:
        print(res[(v, w)])


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor
# Post Order順を使用して判定する
# q = 100000では3分近くかかり、実用に耐えず


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


class LowestCommonAncestor:
    def __init__(self, graph, root):
        self.graph = graph
        self.root = root
        self._cache = {}
        self._dfs()

    def _dfs(self):
        n = self.graph.v
        visited = [False] * n
        parent = [None] * n
        post_order = [0] * n

        stack = [self.root]
        i = 0
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                stack.append(v)
                for e in self.graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        parent[w] = v
                        stack.append(w)
            else:
                post_order[v] = i
                i += 1

        self.post_order = post_order
        self.parent = parent

    def find(self, v, w):
        pos = self.post_order
        i = pos[v]
        j = pos[w]
        if i > j:
            i, j = j, i
            v, w = w, v

        vv = v
        while i < j:
            if (vv, w) in self._cache:
                vv = self._cache[(vv, w)]
                break
            vv = self.parent[vv]
            i = pos[vv]

        self._cache[(v, w)] = vv
        return vv


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    lca = LowestCommonAncestor(g, 0)
    q = int(input())
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        print(lca.find(v, w))


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor


class UnionFind:
    def __init__(self, n):
        self.nodes = [i for i in range(n)]
        self.sizes = [1 for _ in range(n)]

    def union(self, p, q):
        rp = self.root(p)
        rq = self.root(q)
        if self.sizes[rp] > self.sizes[rq]:
            self.nodes[rq] = rp
            self.sizes[rp] += self.sizes[rq]
        else:
            self.nodes[rp] = rq
            self.sizes[rq] += self.sizes[rp]

    def connected(self, p, q):
        return self.root(p) == self.root(q)

    def root(self, p):
        while p != self.nodes[p]:
            self.nodes[p] = self.nodes[self.nodes[p]]
            p = self.nodes[p]

        return p


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class WeightedEdge(Edge):
    __slots__ = ('v', 'w', 'weight')

    def __init__(self, v, w, weight):
        super().__init__(v, w)
        self.weight = weight


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def lca(graph, root, queries):
    index = [set() for _ in range(graph.v)]
    for v, w in queries:
        index[v].add((v, w))

    visited = [False] * graph.v
    stored = [False] * graph.v
    parents = [None] * graph.v
    uf = UnionFind(graph.v)
    res = {}
    stack = [root]
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            stack.append(v)
            for e in graph.adj(v):
                w = e.other(v)
                if not visited[w]:
                    stack.append(w)
                    parents[w] = v
        else:
            stored[v] = True
            p = parents[v]
            rest = set()
            for i, j in index[v]:
                if stored[i] and stored[j]:
                    if uf.connected(i, j) and (i, j) not in res:
                        res[(i, j)] = v
                    else:
                        rest.add((i, j))
                else:
                    index[j].add((i, j))
            index[v] = None
            if p is not None:
                uf.union(p, v)
                index[p].update(rest)

    return res


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    q = int(input())
    qs = []
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        qs.append((v, w))

    res = lca(g, 0, qs)
    for v, w in qs:
        print(res[(v, w)])


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor
# Post Order順を使用して判定する
# q = 100000では時間がかかり過ぎ、実用に耐えず


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


class LowestCommonAncestor:
    def __init__(self, graph, root):
        self.graph = graph
        self.root = root
        self._cache = {}
        self._dfs()

    def _dfs(self):
        n = self.graph.v
        visited = [False] * n
        parent = [None] * n
        post_order = [0] * n

        stack = [self.root]
        i = 0
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                stack.append(v)
                for e in self.graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        parent[w] = v
                        stack.append(w)
            else:
                post_order[v] = i
                i += 1

        self.post_order = post_order
        self.parent = parent

    def find(self, v, w):
        pos = self.post_order
        i = pos[v]
        j = pos[w]
        if i > j:
            i, j = j, i
            v, w = w, v

        vv = v
        while i < j:
            if (vv, w) in self._cache:
                vv = self._cache[(vv, w)]
                break
            vv = self.parent[vv]
            i = pos[vv]

        self._cache[(v, w)] = vv
        return vv


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    lca = LowestCommonAncestor(g, 0)
    q = int(input())
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        print(lca.find(v, w))


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor


class UnionFind:
    def __init__(self, n):
        self.nodes = [i for i in range(n)]
        self.sizes = [1 for _ in range(n)]

    def union(self, p, q):
        rp = self.root(p)
        rq = self.root(q)
        if self.sizes[rp] > self.sizes[rq]:
            self.nodes[rq] = rp
            self.sizes[rp] += self.sizes[rq]
        else:
            self.nodes[rp] = rq
            self.sizes[rq] += self.sizes[rp]

    def connected(self, p, q):
        return self.root(p) == self.root(q)

    def root(self, p):
        while p != self.nodes[p]:
            self.nodes[p] = self.nodes[self.nodes[p]]
            p = self.nodes[p]

        return p


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class WeightedEdge(Edge):
    __slots__ = ('v', 'w', 'weight')

    def __init__(self, v, w, weight):
        super().__init__(v, w)
        self.weight = weight


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def lca(graph, root, queries):
    index = [set() for _ in range(graph.v)]
    for v, w in queries:
        index[v].add((v, w))

    visited = [False] * graph.v
    stored = [False] * graph.v
    parents = [None] * graph.v
    uf = UnionFind(graph.v)
    res = {}
    stack = [root]
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            stack.append(v)
            for e in graph.adj(v):
                w = e.other(v)
                if not visited[w]:
                    stack.append(w)
                    parents[w] = v
        else:
            stored[v] = True
            p = parents[v]
            rest = set()
            for i, j in index[v]:
                if stored[i] and stored[j]:
                    if uf.connected(i, j) and (i, j) not in res:
                        res[(i, j)] = v
                    else:
                        rest.add((i, j))
                else:
                    index[j].add((i, j))
            index[v] = None
            if p is not None:
                uf.union(p, v)
                index[p].update(rest)

    return res


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    q = int(input())
    qs = []
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        qs.append((v, w))

    res = lca(g, 0, qs)
    for v, w in qs:
        print(res[(v, w)])


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor


class UnionFind:
    def __init__(self, n):
        self.nodes = [i for i in range(n)]
        self.sizes = [1 for _ in range(n)]

    def union(self, p, q):
        rp = self.root(p)
        rq = self.root(q)
        if self.sizes[rp] > self.sizes[rq]:
            self.nodes[rq] = rp
            self.sizes[rp] += self.sizes[rq]
        else:
            self.nodes[rp] = rq
            self.sizes[rq] += self.sizes[rp]

    def connected(self, p, q):
        return self.root(p) == self.root(q)

    def root(self, p):
        while p != self.nodes[p]:
            self.nodes[p] = self.nodes[self.nodes[p]]
            p = self.nodes[p]

        return p


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class WeightedEdge(Edge):
    __slots__ = ('v', 'w', 'weight')

    def __init__(self, v, w, weight):
        super().__init__(v, w)
        self.weight = weight


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def lca(graph, root, queries):
    index = [[] for _ in range(graph.v)]
    for v, w in queries:
        index[v].append((v, w))
        index[w].append((v, w))

    visited = [False] * graph.v
    parents = [None] * graph.v
    uf = UnionFind(graph.v)
    res = {}
    stack = [root]
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            stack.append(v)
            for e in graph.adj(v):
                w = e.other(v)
                if not visited[w]:
                    stack.append(w)
                    parents[w] = v
        else:
            p = parents[v]
            rest = []
            for i, j in index[v]:
                if uf.connected(i, j) and (i, j) not in res:
                    res[(i, j)] = v
                else:
                    rest.append((i, j))
            index[v] = None
            if p is not None:
                uf.union(p, v)
                index[p].extend(rest)

    return res


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    q = int(input())
    qs = []
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        qs.append((v, w))

    res = lca(g, 0, qs)
    for v, w in qs:
        print(res[(v, w)])


if __name__ == '__main__':
    run()



Fixed submission:
#!/usr/bin/env python3
# GRL_5_C: Tree - Lowest Common Ancestor


class UnionFind:
    def __init__(self, n):
        self.nodes = [i for i in range(n)]
        self.sizes = [1 for _ in range(n)]

    def union(self, p, q):
        rp = self.root(p)
        rq = self.root(q)
        if self.sizes[rp] > self.sizes[rq]:
            self.nodes[rq] = rp
            self.sizes[rp] += self.sizes[rq]
        else:
            self.nodes[rp] = rq
            self.sizes[rq] += self.sizes[rp]

    def connected(self, p, q):
        return self.root(p) == self.root(q)

    def root(self, p):
        while p != self.nodes[p]:
            self.nodes[p] = self.nodes[self.nodes[p]]
            p = self.nodes[p]

        return p


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class WeightedEdge(Edge):
    __slots__ = ('v', 'w', 'weight')

    def __init__(self, v, w, weight):
        super().__init__(v, w)
        self.weight = weight


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def lca(graph, root, queries):
    index = [set() for _ in range(graph.v)]
    for v, w in queries:
        index[v].add((v, w))

    visited = [False] * graph.v
    stored = [False] * graph.v
    parents = [None] * graph.v
    uf = UnionFind(graph.v)
    res = {}
    stack = [root]
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            stack.append(v)
            for e in graph.adj(v):
                w = e.other(v)
                if not visited[w]:
                    stack.append(w)
                    parents[w] = v
        else:
            stored[v] = True
            p = parents[v]
            rest = set()
            for i, j in index[v]:
                if stored[i] and stored[j]:
                    if uf.connected(i, j) and (i, j) not in res:
                        res[(i, j)] = v
                    else:
                        rest.add((i, j))
                else:
                    index[j].add((i, j))
            index[v] = None
            if p is not None:
                uf.union(p, v)
                index[p].update(rest)

    return res


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    q = int(input())
    qs = []
    for _ in range(q):
        v, w = [int(i) for i in input().split()]
        qs.append((v, w))

    res = lca(g, 0, qs)
    for v, w in qs:
        print(res[(v, w)])


if __name__ == '__main__':
    run()