Ще одна задача про дерева

Розглянемо граф із $N$ вершин, який спочатку не містить ребер. Необхідно обробити $M$ запитів наступних типів:

• Додати ребро з вершини v_1 у вершину v_2, причому v_1 і v_2 знаходяться у різних деревах, а v_2 є коренем свого дерева.

• Перевірити, чи лежать дві вершини $a$ і $b$ в одному дереві.

Розв'язок

Для ефективної реалізації цих операцій використовуємо структуру даних СНМ (система неперетинних множин) зі стисненням шляхів:

int n, m, l[NMAX];
int calc_leader(int v)
{
    if (l[v] != v)
        l[v] = calc_leader(l[v]);
    return l[v];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        l[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &z, &x, &y);
        if (z == 1)
            l[y] = x;
        else
            if (calc_leader(x) == calc_leader(y))
                printf("YES\n");
            else
                printf("NO\n");
    }
}

Ваша задача — побудувати такий тест, на якому цей розв'язок працюватиме довгий час. Точніше, потрібно зробити тест, на якому кількість викликів функції calc_leader буде не менше \frac{1}{4} M \log_2 M.