Коли у нас є задача, де потрібно знайти мінімальне кістякове дерево і ребра задані неявно, то часто буває корисно подумати в сторону алгоритму Борувки.
Далі йде приблизний опис алгоритму Борувки (для кращого розуміння погугліть):
У будь-який момент часу алгоритму наші вершини будуть розбиті на множини, причому вершини з однієї множини вже пов'язані між собою, а вершини з різних ні. Далі, ми повинні якимось чином знайти вагу мінімального ребра, що виходить з кожного числа й допровести ці ребра. Кількість множин зменшиться як мінімум в рази, тобто кількість ітерацій нашого алгоритму не більш логарифмічна від числа вершин.
Таким чином, все що нам залишилося, це вміти знаходити вагу мінімального ребра, що виходить з множини. Для цього, для кожного числа знайдемо інше число , таке що (a_i + a_j) \bmod M мінімально і числа належать різним множинам. Це можна робити зберігаючи всі числа в сеті, потім видаляти всі числа з однієї множини, знаходити для кожного з них оптимальне (за допомогою lower bound), повертати ці числа назад.