MathNet 2025 — 50 problems with figures (EN–VI) Question 14

A graph is *good* if its edges can be colored with 2 colors so that no cycle has two consecutive edges of the same color. What is the maximum number of edges in a *good* graph with 1000 vertices?