HA_57

/*
 * Вход:
 *   n                        — количество вершин (0 … n-1)
 *   затем n строк:           — описание каждой вершины
 *     <буква>  <left> <right>
 *       буква  – символ 'A' … 'Z' в самой вершине
 *       left   – индекс левого ребёнка или −1
 *       right  – индекс правого ребёнка или −1
 *
 * Корень – та вершина, которая нигде не встречается как чайлд.
 */

/*
7
A 1 2
B 3 4
C 5 6
D -1 -1
E -1 -1
F -1 -1
E -1 -1
*/

#include <bits/stdc++.h>
// Так вызываются все стандартные библиотеки
using namespace std;

struct Node {
    char c;     // буква
    int  left;  // индекс левого чайлда или -1
    int  right; // индекс правого чайлда или -1
};

// информация, которую храним в хэше для каждой маски
struct Info {
    int idx;   // вершина
    int size;  // размер поддерева
};

vector<Node> tree;                       // сами вершины
unordered_map<uint32_t, Info> seenMask;  // mask → лучшая вершина
pair<int,int> firstPair{-1,-1};          // ответ на «лёгкую» версию
pair<int,int> bestPair{-1,-1};           // ответ на «сложную» версию
int bestSum = -1;                        // максимум size(u)+size(v)

/* DFS возвращает:
 *   mask  — 26-битная маска букв поддерева
 *   size  — количество вершин поддерева
 */
pair<uint32_t,int> dfs(int v)
{
    if (v == -1) return {0u, 0};

    auto [mL, sL] = dfs(tree[v].left);
    auto [mR, sR] = dfs(tree[v].right);

    uint32_t myMask = mL | mR | (1u << (tree[v].c - 'A'));
    int      mySize = sL + sR + 1;

    auto it = seenMask.find(myMask);

    // первая пара дублей → ответ «лёгкой» задачи
    if (it != seenMask.end() && firstPair.first == -1)
        firstPair = {it->second.idx, v};

    // обновляем максимум для «сложной» версии
    if (it != seenMask.end()) {
        int curSum = it->second.size + mySize;
        if (curSum > bestSum) {
            bestSum = curSum;
            bestPair = {it->second.idx, v};
        }
        // в таблице оставляем вершину с бОльшим поддеревом —
        // это для следующих сравнений
        if (mySize > it->second.size)
            it->second = {v, mySize};
    } else {
        seenMask.emplace(myMask, Info{v, mySize});
    }

    return {myMask, mySize};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    tree.resize(n);
    for (int i = 0; i < n; ++i) {
        char ch; int l, r;
        cin >> ch >> l >> r;
        tree[i] = {ch, l, r};
    }

    /* определяем корень: тот,
    кто не является ничьим чайлдом */
    vector<int> isChild(n, 0);
    for (auto &v : tree) {
        if (v.left  != -1) isChild[v.left]  = 1;
        if (v.right != -1) isChild[v.right] = 1;
    }
    int root = find(isChild.begin(), isChild.end(), 0) - isChild.begin();
    if (root == n) { cerr << "root not found\n"; return 0; }

    dfs(root);

    if (firstPair.first == -1)
        cout << "No equivalent vertices\n";
    else {
        cout << "Easy version pair: "  << firstPair.first << ' ' << firstPair.second << '\n';
        cout << "Hard version pair: "  << bestPair.first  << ' ' << bestPair.second
             << " (sum = " << bestSum << ")\n";
    }
    return 0;
}