Bump this problem !

this one impossible

Anyone interested can find the official solution in russian on this web page: https://olympiads.mccme.ru/vmo/.

first of all if we choose $N-k$ vertices and choose one outgoing edge from each such that there is no directed cycle then we have system of k cities and $N-k$ roads, with the conditions of the problem, and this graph can be devided to some connected components(if we do not consider directions) such that there exist exactly one vertex in each connected component that does not have a outgoing edge. back to problem and use induction on $N-k:$ $N-k=1$ is ok. So we consider for $N-k-1$ we had chosen $v_1 ,v_2 , \cdots ,v_{N-k-1}$ and outgoing edge $e_i$ of $v_i$ and the graph is devided to connected components $s_1,s_2, \cdots , s_{k+1}$ now for $N-k$ if we consider we choose the minimum case of $N-k$ cities and one outgoing edge from each.by pigeon hole principle we find out that there is $j$ such that we choose all vertices of $s_j$ and if WLOG $j=1$ and $v_1,v_2, \cdots ,v_r,x$ are vertices of $s_1$ (r can be 0) and $ E_1,E_2,\cdots,E_r ,E_x$ are edges that we had chosen ($E_i$ of $v_i$)and $E_{r+1},\cdots,E_{N-k-1}$are rest of them(not necessarily$E_i $of $v_i$). we can claim that this system is minimum too: $v_1,v_2,\cdots,v_r,x,v_{r+1},v_{r+2},\cdots,v_{N-k-1}$ $E_1,E_2,\cdots,E_r,E_x,e_{r+1},e_{r+2},\cdots,e_{N-k-1}$ because it does not have a directed cycle and also we must prove that: $e_{r+1}+e_{r+2}+\cdots+e_{N-k-1} \leq E_{r+1}+E_{r+2}+\cdots+E_{N-k-1}$ if this is not true we must have $e_1,e_2,\cdots ,e_r, E_{r+1},\cdots,E_{N-k-1}$ is minimum case for $N-k-1$ that is contradiction(because it does not have directed cycle ) so induction hypothesis is also true for $N-k$ and problem solved.