頂点 \(1\) と繋がっている辺 \((1,i) \ (2 \leq i \leq N)\) の色を全て質問します。

\((1,i)\) が赤で塗られていれば頂点 \(i\) を赤い頂点とし、青で塗られていれば頂点 \(i\) を青い頂点とします。
また、各頂点 \(i \ (2 \leq i \leq N)\) の上に石を \(1\) つずつ置きます。

以下の操作を行います。

1. 石が置かれている赤い頂点と、石が置かれている青い頂点を \(1\) つずつ選び、それぞれ \(x,y\) とする。辺 \((x,y)\) の色を質問する。
2. 辺 \((x,y)\) が赤で塗られていれば頂点 \(y\) に置かれた石を取り除き、青で塗られていれば頂点 \(x\) に置かれた石を取り除く。
3. 「全ての赤い頂点の石が取り除かれた」または「全ての青い頂点の石が取り除かれた」を満たすならば操作を終了する。そうでなければ \(1\) に戻る。

操作 \(2\) より、石が取り除かれた赤い頂点 \(x\) は、青い頂点と青い辺で繋がっていることになります。
よって、「全ての赤い頂点の石が取り除かれた」状態で操作が終了した場合を考えると、全ての赤い頂点はいずれかの青い頂点と青で塗られた辺で繋がっていることになります。

つまり、(赤い頂点)-(青い頂点)-(頂点 \(1\)) が青い辺のみで繋がります。これにより、各頂点 \(i \ (2 \leq i \leq N)\) が赤い頂点か青い頂点かに関わらず、青い辺のみで頂点 \(1\) と連結になっています。よって、青い辺のみの全域木が見つかります。

全ての青い頂点の石が取り除かれた場合も同様です。

必要な質問回数を見積もります。
はじめに 辺 \((i,1)\) の色を特定するのに \(N-1\) 回の質問が必要です。
また、操作を繰り返す回数(石を取り除く回数)は高々 \(N-2\) 回であるため、必要な質問の回数も高々 \(N-2\) 回です。
よって \(2N-3\) 回の質問で、全ての辺が同じ色で塗られた全域木を見つけることができます。
また、各操作は \(O(1)\) で行えるため、全体として計算量は \(O(N)\) になります。