Powerful Strongholds

In a small world not so far away, there is an ongoing war between two nations, A and B. There are n (3 ≤ n ≤ 20) strongholds in this world, with roads between some of them. Two strongholds are neighbors if there is a road between them, all roads are bidirectional. The Chef is at war and he recently came up with a scheme that will help his country to never lose the war. He would like to select a se