Q18 Matemática  (Baltic Way 2009)

Seja $n>2$ um inteiro. Em um país existem $n$ cidades e cada duas delas são conectadas por uma estrada direta. A cada estrada é atribuído um número inteiro do conjunto $\{1,2,\dots ,m\}$ (estradas diferentes podem receber o mesmo número). A prioridade de uma cidade é a soma dos números atribuídos às estradas que levam a ela. Encontre o menor $m$ para o qual é possível que todas as cidades tenham uma prioridade diferente.