Jeśli ktoś jest zainteresowany - poniżej moje rozwiązanie z zastrzeżeniem, że nie mam pełnego dowodu na to, że zawsze mieści się w limicie operacji (aczkolwiek max na testach to ~530K). Losuję kolejność przeglądania wierzchołków żeby nieco zabezpieczyć się przed złośliwymi testami.

Rozwiązanie składa się z dwóch części. W pierwszej staramy znaleźć się w takim wierzchołku, że:
(A) Wiemy na 100% że do niego weszliśmy, pomimo że
(B) wierzchołek nie został potwierdzony (jest to "nieparzysty sukces"), oraz
(C) wierzchołek ma co najmniej 2 sąsiadów.
Jedyny przypadek, kiedy jest to niemożliwe, to gwiazda z centrum w wierzchołku 1 - taką sytuację jesteśmy w stanie wykryć i obsłużyć.

Robimy to szukając jak najkrótszych "potwierdzonych sekwencji" (tzn. od pozytywnej do pozytywnej odpowiedzi sondy) między różnymi wierzchołkami. Będąc w danym "potwierdzonym" wierzchołku, mamy 3 możliwości:
[1] Jesteśmy w danym wierzchołku po raz pierwszy. Chcemy znaleźć dowolną "potwierdzoną sekwencję" do innego wierzchołka. Możemy to zrobić próbując każdego potencjalnego sąsiada i próbować przejść z niego do każdego z pozostałych N-2 wierzchołków. Niepowodzenie oznacza gwiazdę.
[2] Znamy już "potwierdzoną sekwencję" z naszego wierzchołka. Próbujemy ją skrócić - jeśli poprzednio było to V(1) - W1(0) - W2(0) - ... - Wn(0) - Z(1), to teraz próbujemy V1(1) - W2 - ... -Wn - Z. Jeśli po drodze dostaliśmy odpowiedź pozytywną, to mamy krótszą sekwencję. Jeśli dotarliśmy do końca bez potwierdzenia, to znaczy że V - W1 - Z jest istniejącą ścieżką, a więc idealną "potwierdzoną sekwencją". Zgubiliśmy się, więc szukamy jakiegokolwiek potwierdzonego wierzchołka.
[3] Znamy "potwierdzoną sekwencję" długości 2 - przechodzimy do środkowego wierzchołka tej sekwencji. Spełnia on kryteria (A)-(C).

Druga część rozwiązania to już wyznaczanie drzewa rozpinającego grafu, rozpoczynając od wierzchołka R spełniającego kryteria (A)-(C).
[1] Będąc w niepotwierdzonym wierzchołku, bardzo łatwo możemy wyznaczyć listę sąsiadów
[2] Dla każdego sąsiada N1 wierzchołka R chcemy wyznaczyć również jego listę sąsiadów. Robimy to przy pomocy dodatkowego sąsiada R - N2.
(a) Jeśli sekwencja R(0)->N1(1)->N2(0)->R(?) zakończy się potwierdzeniem, to znaczy że N1-N2-R stanowią trójkąt. R jest obecnie potwierdzony, więc możemy przejść do każdego z jego sąsiadów jako niepotwerdzonego i wywołać przeszukiwanie rekurencyjnie.
(b) Wpp. między N1 a N2 nie ma krawędzi. Żeby przetestować istnienie krawędzi N1-V, wykonujemy sekwencję N1(1)->V(0)->N2(?). Jeśli mamy potwierdzenie dla N2, to istnieją krawędzie N1-V-N2. Jeśli nie, to przedłużamy: N1(1)->V(0)->N2(0)->R(0)->N2(?). Ostatni ruch wykonaliśmy z V lub R. W zależności od tego, czy się powiódł, wiemy w którym z nich byliśmy i czy krawędź N1-V istnieje.
[3] Mając teraz sąsiadów sąsiadów R, możemy do nich wejść jako niepotwierdzonych i wykonać przeszukanie rekurencyjnie.

Ja miałem prawie tak samo z dokładnością do:
Jak mam potwierdzoną ścieżkę V0 - V1 - ... - Vm i chcę ją skrócić, to biorę jakiś jej prefix długości k i pytam o: V0, V1, ... Vk, Vm. Jak dostałem true, to skracam ścieżkę do V0, V1, ... Vk, Vm, jak false to do V0, V{k+1}, V{k+2}, ... Vm. Na początku dzieliłem na pół jak to w binsearchu, ale potem sprawdziłem doświadczalnie, że lepiej się sprawdza wzięcie trochę dłuższego prefixu, około 0.8 * długość całej ścieżki.
Dopisałem jeszcze takie dwa opty: jak się zgubiłem, to sortuję wszystkie wierzchołki, na których nie wywołałem MoveProbe od ostatniego potwierdzonego ruchu rosnąco po długości potwierdzonej sekwencji, a te które jeszcze nie mają przypisanej sekwencji daję na sam koniec i wywołuję się na nich w tej kolejności.
Jak szukam pierwszej potwierdzonej sekwencji, to wybieram losową permutację wszystkich wierzchołków, generuję jej wszystkie przesunięcia cykliczne, przeglądam je w losowej kolejności i iteruję się po wszystkich wierzchołkach w takiej kolejniści jak w danym przesunięciu cyklicznym

Z tymi wszystkimi optami najgorszy wynik z paczek 4-10 to 401151 zapytań na 10j (mniej niż moje rozwiązanie do subtaska 3, które najwięcej wykonało 551188 zapytań)