class Solution {
 public:
  vector<int> closestNode(int n, vector<vector<int>>& edges,
                          vector<vector<int>>& query) {
    vector<int> ans;
    vector<vector<int>> graph(n);
    vector<vector<int>> dist(n, vector<int>(n, -1));

    for (const auto& e : edges) {
      const int u = e[0];
      const int v = e[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    for (int i = 0; i < n; ++i)
      fillDist(graph, i, i, 0, dist);

    for (const auto& q : query) {
      const int start = q[0];
      const int end = q[1];
      const int node = q[2];
      ans.push_back(findClosest(graph, dist, start, end, node, start));
    }

    return ans;
  }

 private:
  void fillDist(const vector<vector<int>>& graph, int start, int u, int d,
                vector<vector<int>>& dist) {
    dist[start][u] = d;
    for (const int v : graph[u])
      if (dist[start][v] == -1)
        fillDist(graph, start, v, d + 1, dist);
  }

  int findClosest(const vector<vector<int>>& graph,
                  const vector<vector<int>>& dist, int u, int end, int node,
                  int ans) {
    for (const int v : graph[u])
      if (dist[v][end] < dist[u][end])
        return findClosest(graph, dist, v, end, node,
                           dist[ans][node] < dist[v][node] ? ans : v);
    return ans;
  }
};

class Solution {
  public int[] closestNode(int n, int[][] edges, int[][] query) {
    int[] ans = new int[query.length];
    List<Integer>[] graph = new List[n];
    int[][] dist = new int[n][n];
    Arrays.stream(dist).forEach(A -> Arrays.fill(A, -1));

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] e : edges) {
      final int u = e[0];
      final int v = e[1];
      graph[u].add(v);
      graph[v].add(u);
    }

    for (int i = 0; i < n; ++i)
      fillDist(graph, i, i, 0, dist);

    for (int i = 0; i < query.length; ++i) {
      final int start = query[i][0];
      final int end = query[i][1];
      final int node = query[i][2];
      ans[i] = findClosest(graph, dist, start, end, node, start);
    }

    return ans;
  }

  private void fillDist(List<Integer>[] graph, int start, int u, int d, int[][] dist) {
    dist[start][u] = d;
    for (final int v : graph[u])
      if (dist[start][v] == -1)
        fillDist(graph, start, v, d + 1, dist);
  }

  private int findClosest(List<Integer>[] graph, int[][] dist, int u, int end, int node, int ans) {
    for (final int v : graph[u])
      if (dist[v][end] < dist[u][end])
        return findClosest(graph, dist, v, end, node, dist[ans][node] < dist[v][node] ? ans : v);
    return ans;
  }
}

class Solution:
  def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
    ans = []
    graph = [[] for _ in range(n)]
    dist = [[-1] * n for _ in range(n)]

    for u, v in edges:
      graph[u].append(v)
      graph[v].append(u)

    def fillDist(start: int, u: int, d: int) -> None:
      dist[start][u] = d
      for v in graph[u]:
        if dist[start][v] == -1:
          fillDist(start, v, d + 1)

    for i in range(n):
      fillDist(i, i, 0)

    def findClosest(u: int, end: int, node: int, ans: int) -> int:
      for v in graph[u]:
        if dist[v][end] < dist[u][end]:
          return findClosest(v, end, node, ans if dist[ans][node] < dist[v][node] else v)
      return ans

    return [findClosest(start, end, node, start)
            for start, end, node in query]