VN-TST 1997 Problem 2

There are $25$ towns in a country. Find the smallest $k$ for which one can set up two-direction flight routes connecting these towns so that the following conditions are satisfied:

1. from each town there are exactly $k$ direct routes to $k$ other towns;
2. if two towns are not connected by a direct route, then there is a town which has direct routes to these two towns.