C. Treasure Hunt
graphs; interactive
All problems in this contest share the same statement, the only difference is the test your solution runs on. For further information on scoring please refer to ""Scoring"" section of the statement.This is an interactive problem.Imagine you are a treasure hunter, a very skillful one. One day you came across an ancient map which could help you to become rich. The map shows multiple forestry roads, and at each junction there is a treasure. So, you start your journey hoping to retrieve all the hidden treasures, but you don't know yet that there is a wicked wizard standing against you and craving to tangle up these roads and impede your achievements.The treasure map is represented as an undirected graph in which vertices correspond to junctions and edges correspond to roads. Your path begins at a certain fixed vertex with a label known to you. Every time you come to a vertex that you have not been to before, you dig up a treasure chest and put a flag in this vertex. At the initial vertex you'll find a treasure chest immediately and, consequently, you'll put a flag there immediately as well.When you are standing at the junction you can see for each of the adjacent vertices its degree and if there is a flag there. There are no other things you can see from there. Besides, the power of the wicked wizard is so great that he is able to change the location of the roads and junctions on the map without changing the graph structure. Therefore, the sequence of the roads coming from the junction \(v\) might be different each time you come in the junction \(v\). However, keep in mind that the set of adjacent crossroads does not change, and you are well aware of previously dug treasures at each adjacent to \(v\) vertex.Your goal is to collect treasures from all vertices of the graph as fast as you can. Good luck in hunting!