12. In a regular 2018-gon, a line segment is drawn between every two vertices, and each segment is colored either red or blue. Find the minimum number of triangles in this figure whose three sides are all the same color.
Let $N$ be the number of triangles in this graph with all three sides of the same color, and $M$ be the number of triangles with not all three sides of the same color. Let $x_{i}$ be the number of red segments with the $i$-th vertex as an endpoint. Then we have
$$
M+N=C_{2018}^{3}, \sum_{i=1}^{2018} x_{i}\left(2017-x_{i}\right)=2 M
$$

$N$ reaches its minimum value $C_{2018}^{3}-1009^{2} \times 1008=2 C_{1009}^{3}$ if and only if each $x_{i}=1008$ or 1009.
(16 points)
$N=2 C_{1009}^{3}$ can be achieved, for example, by coloring the segments
$$
i \rightarrow i \pm j(\bmod 2018) \quad(1 \leq i \leq 2018,1 \leq j \leq 504)
$$

red, and coloring the other segments blue.
(22 points)