6. In the Empire of Westeros, there were 1000 cities and 2017 roads (each road connected some two cities). From any city, you could travel to any other. One day, an evil wizard enchanted $N$ roads, making it impossible to travel on them. As a result, 7 kingdoms formed, such that within each kingdom, you could travel from any city to any other by roads, but you could not travel from one kingdom to another by roads. What is the largest $N$ for which this is possible?
# Answer 1024.

Solution: Suppose the evil wizard enchanted all 2017 roads. This would result in 1000 kingdoms (each consisting of one city). Now, imagine that the good wizard disenchants the roads so that there are 7 kingdoms. He must disenchant at least 993 roads, as each road can reduce the number of kingdoms by no more than 1. Therefore, the evil wizard could not have enchanted more than 2017-993=1024 roads.

For graders: Partial credit can be given for a correct answer obtained for a specific case - without a general proof.

## Variant 3-b