CMO 2023 Problem 5

A country with $n$ cities has some two-way roads connecting certain pairs of cities. Someone notices that if the country is split into two parts in any way, then there would be at most $k n$ roads between the two parts (where $k$ is a fixed positive integer). What is the largest integer $m$ (in terms of $n$ and $k$ ) such that there is guaranteed to be a set of $m$ cities, no two of which are directly connected by a road?