Let ~E_\text{yes}~ be the set of edges about which the contestant has answered "yes" (connected), ~E_\text{no}~ the set of edges about which contestant has answered "no", and ~E_\text{maybe}~ the rest of the edges, whose statuses are not yet determined. Also, let ~G = (V, E_\text{yes})~ and ~H = (V, E_\text{yes} \cup E_\text{maybe})~. ~G~ is the graph you get by assuming that all edges in ~E_\text{maybe}~ are not connected, while ~H~ is the graph you get by assuming that all edges in ~E_\text{maybe}~ are connected.

Initially, ~G~ is empty and thus not connected, while ~H~ is connected. In order not to reveal any clue to the judge, the contestant should maintain the invariant: ~G~ should always be disconnected, while ~H~ should always be connected.

There are several possible ways to maintain the invariant.

An ~\mathcal O(n^4)~ solution

When asked by the judge whether an edge ~e = (u, v)~ is connected, answer "no" if and only if ~e~ is part of a cycle in ~H~. One can see that this does not change the connectivity of ~G~ and ~H~.

To decide whether ~e~ forms a circle, one can perform a depth-first search to find out whether there is a path from ~u~ to ~v~ in ~(V, E_\text{yes} \cup E_\text{maybe} - (u, v))~. This is an ~\mathcal O(n^2)~ operation. As there are ~\mathcal O(n^2)~ edges, the total running time is ~\mathcal O(n^4)~.

In other words, we answer "yes" if and only if ~e~ is a bridge in ~H~.

An ~\mathcal O(n^2)~ solution

Given a vertex ~v~, let ~D(v)~ be the connected component ~v~ belongs to in ~G~. We maintain two data structures:

1. ~R~ is a table mapping each ~v~ to a representative of ~D(v)~.
2. ~S~ is a symmetric matrix indexed by ~V~. For ~u~ and ~v~ in ~V~, if ~R(u) \ne R(v)~, ~S(R(u), R(v))~ is the number of edges, in ~E_\text{maybe}~, that connects ~D(u)~ and ~D(v)~.

The contestant answers "yes" to query ~(u, v)~ if and only if ~S(R(u), R(v)) = 1~.

~R~ can be implemented as a disjoint-set linked list. Each disjoint set is represented by a linked list of its elements, and the representative is the one at the head. Each element has a pointer to its representative. To unite two sets, we connect the lists and update the pointers. A union takes ~\mathcal O(n)~ time and a find takes ~\mathcal O(1)~ time.

As for ~S~, initially ~S(u, v) = 1~ unless ~u = v~. Whenever the judge asks about ~(u, v)~, ~S~ is updated as follows.

1. If the contestant answers "no", we decrement ~S(R(u), R(v))~ by ~1~.
2. If the contestant answers "yes", let ~w~ be the representative after uniting ~D(u)~ and ~D(v)~. For each ~x~ that is a representative of some connected component, both ~S(w, x)~ and ~S(x, w)~ are updated to ~S(R(u), x) + S(R(v), x)~.

There can be at most ~n-1~ unions, thus the total time spent on union is ~\mathcal O(n^2)~. An update of ~S~ requires ~\mathcal O(1)~ time for a "no" response, and ~\mathcal O(n)~ time for a "yes" response. Since the graph ~G~ is a tree, we respond "yes" exactly ~n-1~ times. Thus the time spent on updating ~S~ is also ~\mathcal O(n^2)~. We thus have an ~\mathcal O(n^2)~ algorithm.

A One-Liner ~\mathcal O(n^2)~ Algorithm

There is a surprising one-line ~\mathcal O(n^2)~ algorithm:

#include "game.h"

void initialize(int n) {
    // DO NOTHING!
}

int c[1500];
int hasEdge(int u, int v) {
    return ++c[u > v ? u : v] == (u > v ? u : v);
}

To understand the algorithm, imagine that we partition the set of all the possible edges into ~E_1, E_2, \dots, E_{n-1}~, with ~E_i = \{(i, j) \mid i > j\}~. Each ~E_i~ has exactly ~i~ possible edges. The algorithm above answers "yes" to ~(u, v)~ (where ~u > v~) if it is the last edge in ~E_u~ that is queried.

To see how it works, consider the last query. Denote the queried edge by ~e~, and the graph ~G = (V, E_\text{yes}-e)~. The contestant wins if ~G~ is disconnected, while ~G+e~ is connected.

• ~G~ is disconnected, since it contains only ~n-2~ edges.
• ~G+e~ is connected, since it contains ~n-1~ edges, and there is no cycle in ~G+e~. One can see that there is no cycle since, in each ~E_i~, we answer yes to only one edge. Formally, if there is a cycle ~C~ in ~G+e~, considering the node ~u~ in ~C~ with largest id, ~E_u~ must have exactly one edge in ~G+e~. But ~u~ has two neighbors in ~C~ with smaller ids, a contradiction.