KMO 2019 Problem 8

There are two countries $A$ and $B$ , where each countries have $n(\ge 2)$ airports. There are some two-way flights among airports of $A$ and $B$ , so that each airport has exactly $3$ flights. There might be multiple flights among two airports; and there are no flights among airports of the same country. A travel agency wants to plan an exotic traveling course which travels through all $2n$ airports exactly once, and returns to the initial airport. If $N$ denotes the number of all exotic traveling courses, then prove that $\frac{N}{4n}$ is an even integer.

(Here, note that two exotic traveling courses are different if their starting place are different.)