A ambição de conquista e expansão é uma doença muito conhecida no planeta Terra... E também em todo o universo.

No planeta "Imperius" várias fortalezas foram construídas uma de cada vez e cada uma delas, menos a primeira, estavam ligadas no momento da sua construção para uma fortaleza previamente construída por um caminho direto, para fins comerciais.

Imperius estava se tornando um dos planetas mais pacífico e próspero no universo, até que eles pararam de construir mais fortalezas. Naquele momento, surgiram N diferentes impérios (numeradas de 1 a N), cada um deles dominando uma fortaleza diferente. E a sede de conquista se apoderou de Imperius. Assim, a cada ano, exatamente um dos impérios vivos conquista cada império vizinho, e domina cada fortaleza pertencente a eles. Dois impérios são considerados vizinhos se existem duas fortalezas unidas por um caminho, cada uma dominada por um império diferente destes dois.

Eventualmente um único império vai dominar cada fortaleza. Sua tarefa é encontrar o número mínimo de anos que isso pode acontecer.

Como um exemplo, no lado esquerdo da figura abaixo um cenário possível é mostrado, onde seis fortalezas são inicialmente dominadas por seis impérios diferentes. Cada fortaleza é identificada com o número do império que a domina. Se o império 2 conquistou cada vizinho no primeiro ano, a situação seria como na figura central. Finalmente, se o império 5 conquistou seus impérios vizinhos, ele acabaria dominando cada fortaleza, como pode ser visto no lado direito da figura.