The (Eleventh) Doctor and River Song decide to play a game on a directed acyclic graph G, which has one source vertex s and one sink vertex t.2 Each player has a token on one of the vertices of G. At the start of the game, The Doctor's token is on the source s, and River's token is on the sink t. The players alternate turns, with The Doctor moving first. On each of his turns, the Doctor moves his token forward along a directed edge; on each of her turns, River moves her token backward along a directed edge. If the two tokens ever meet on the same vertex, River wins the game. ("Hello, Sweetie!") If the Doctor's token reaches t or River's token reaches s before the two tokens meet, then the Doctor wins the game. Describe and analyze an alg