Alice and Bob are playing a game on a simple undirected graph with vertices labeled from to and edges. Initially, a token is placed on vertex .
They play in turns, and Alice plays first. In each turn:
Bob may end the game at any moment, including before the first turn. When the game ends, the label of the vertex containing the token is called the outcome.
Alice wants the outcome to be as small as possible. Bob wants the outcome to be as large as possible. Both players play optimally.
For each test case, determine the largest possible outcome that Bob can guarantee.
The token starts on the only vertex, so Bob can end the game immediately and get outcome .
The graph is a path. Whenever Bob is at vertex , Alice can mark the only edge leaving it. Therefore Bob cannot guarantee reaching a larger label, and the answer is .
Alice can mark only one of the two edges leaving vertex . Bob can move through the other one and guarantee an outcome of at least . However, Alice can stop Bob from guaranteeing vertex , so the answer is .
The graph is complete on four vertices. Bob cannot guarantee reaching vertex , because Alice can always mark the edge leading to it. But Bob can guarantee reaching either vertex or vertex , so the answer is .
Bob cannot guarantee reaching vertex alone, because Alice can block the needed edge whenever there is only one way toward it. But vertices and together give Bob enough choices to force reaching a vertex with label at least .