There are some important details not translated properly. 1) There are exactly $3$ roads coming from every city. 2) Prime minister moves first. The president(second player) always wins. Let $G$ be the corresponding graph. Suppose the two players consecutively color the edges of $G$ with one of three colors $0,1,2$. The Premier goes first and colors an edge $v_0\,v_1$ with color $0$. Then the President colors $v_1\,v_2$ with color $1$. He threatens to make the edges incident to $v_1$ with different colors. To prevent it, the Premier colors the third edge from $v_1$ , $v_1\,x_1$ with $0$ or $1$. The presidents proceed of coloring $v_2\,v_3$ with $0$ thus forces the premier to color $v_2\,x_2$ somehow to prevent again different coloring of the vertex $v_2$ The second player proceed in that way, till he/she reaches(and colors) an edge $v_{n-1}\,v_n$ and $v_n$ is connected with some vertex among $v_0,x_1,x_2,\dots,x_{n-1}$ , say $x_j$. At his next turn he/she colors $v_n\,x_j$ with a color different from the colors of $x_{n-1}\,x_n$ and $v_j\,x_j$ . Thus, the president threatens to make different colored edges at the vertices $v_n$ and at $x_j$ . This "fork" cannot be handled by the premier and he/she loses. Comment. The Russians don't publish online solutions of the Saint Peterburg competition, probably because the authors release every year a book (paper) with those and similar problems. The author of the problem is D. Karpov, which is also the author of a problem at this year competition, which in my opinion is more interesting http://artofproblemsolving.com/community/c6h1498367p8825831 (unfortunately I can't manage it).