The bfs method is suspect.
- How can you tell whether a city is protected by more than one soldier? You would expect used[v] to have a value greater than 1, but that can never happen because of the if (used[v] == 0) check.
- How do you check how far a soldier can protect cities? The cnt == d check isn’t correct, and you’ll need to put the distance onto the queue along with the city number.