Задача из яндекс контест по графам. 2 варианта кода, один проходит все тесты другой нет, почему?

Ниже представлены два кода, тот, что на Python мой. На плюсах взял из инета. Алгоритм на плюсах проходит все тесты. Мой не проходит 6 тест (не знаю точно какие входные данные). Помогите разобраться в чем может быть ошибка и на каких входных данных может мой код выдавать ошибку. Моя фантазия на тесты иссякла, два дня сидел придумывал разные тесты, но так и не нашёл в чём дело. Я использую DFS, алгоритм на плюсах - BFS

Задача В заданном корневом дереве найдите вершины, максимально удалённые от корня. Расстоянием между вершинами считается количество рёбер в пути.

Формат ввода В первой строке задано n — количество вершин в дереве (1 ≤ n ≤ 100). В следующих n − 1 строках заданы вершины, являющиеся предками вершин 2, 3, …, n. Вершина 1 является корнем дерева.

Формат вывода В первой строке выведите максимальное расстояние от корня до остальных вершин дерева. Во второй строке выведите, сколько вершин дерева находятся от корня на таком расстоянии. В третьей строке выведите номера этих вершин через пробел в порядке возрастания.

Пример 1

    Ввод    
    3
    1
    1
    
    Вывод
    1
    2
    2 3
    


 Пример 2
    
    Ввод    
    3
    1
    2
    
    Вывод
    2
    1
    3

Python

count = int(input())

graph = {}
costs = {}
for i in range(count):
    graph[i + 1] = []
      
for i in range(count - 1):
    parent = int(input())
    graph[parent].append(i + 2)      

costs[1] = 0
def dfs(head, max_dist):
    for node in graph[head]:    
        costs[node] = costs[head] + 1
        if costs[node] >  max_dist:
            max_dist = costs[node]    
        max_dist = dfs(node, max_dist)

    return max_dist   

max_dist = dfs(1, 0)  
print(max_dist)

count_max = 0
answer = []
for item in costs.keys():
    if costs[item] == max_dist:
        count_max += 1
        answer.append(item) 

print(count_max)
print(' '.join([str(item) for item in answer]))

C++

#include <algorithm>
#include <queue>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    vector<vector<int> > gr(n+1);
    for (int i = 2; i <= n; ++i) {
        int a;
        cin >> a;
        gr[a].push_back(i);
    }
    
    vector<int> nodes;
    queue<int> q;
    q.push(1);
    int depth = -1;
    while (!q.empty()) {
        int m = q.size();
        depth += 1;
        nodes.clear();
        for (int i = 0; i < m; ++i) {
            int u = q.front();
            nodes.push_back(u);
            q.pop();
            for (const auto& v : gr[u]) {
                q.push(v);
            }
        }
    }
    
    sort(nodes.begin(), nodes.end());
    
    cout << depth << "\n" << nodes.size() << "\n";
    
    for (const auto& u : nodes) {
        cout << u << " ";
    }
    return 0;
}