Q21 Matemática  (Tournament Of Towns 2004)

Temos várias cidades, com linhas de ônibus entre algumas delas (cada linha de ônibus vai de uma cidade a outra sem paradas). Sabe-se que você pode ir de qualquer cidade a qualquer outra de ônibus (possivelmente mudando de ônibus várias vezes). O Sr. Ivanov comprou uma passagem para cada uma das rotas de ônibus (uma passagem permite viagem única em qualquer direção, mas não retornando na mesma rota). O Sr. Petrov comprou n passagens para cada uma das rotas de ônibus. Tanto Ivanov quanto Petrov começaram na cidade A. Ivanov esgotou todos os seus ingressos sem comprar nenhum novo e terminou sua viagem na cidade B. Petrov, depois de usar alguns de seus ingressos, ficou preso na cidade X: ele não pode sair sem comprar um novo bilhete. Prove que X é A ou B.