# https://leetcode.com/problems/find-closest-node-to-given-two-nodes

from typing import List

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        node1_dist = [-1] * len(edges)
        node2_dist = [-1] * len(edges)

        def traverse(node, edges, dist_list):
            dist = 0
            dist_list[node] = 0
            while edges[node] != -1:
                node = edges[node]
                dist += 1
                if dist_list[node] != -1:
                    break
                dist_list[node] = dist

        traverse(node1, edges, node1_dist)
        traverse(node2, edges, node2_dist)
        result = -1
        now = float('inf')
        for i in range(len(edges)):
            if node1_dist[i] == -1 or node2_dist[i] == -1:
                continue
            if now > max(node1_dist[i], node2_dist[i]):
                result = i
                now = max(node1_dist[i], node2_dist[i])
        return result