The road less traveled

Probability Level 3

Suppose a small country has $15$ cities and $70$ roads, where each road directly connects precisely $2$ cities. What is the largest possible number of cities that are directly connected to every other city in the country?