Some cities of Russia are connected with some cities of Ukraine with international airlines. The Interstate Council for the Promotion of Migration intends to introduce a one-way traffic on each airline so that, by taking off from the city, it could no longer be returned in this city (using other one-way airlines). Prove that the number of ways to do this is not divided by $3$.
In other words: we are given a bipartite graph $G$ and wish to show the number of acyclic orientations it has is not a multiple of 3. It is known that the number of such orientations is $|\chi_G(-1)|$, where $\chi_G$ is the chromatic polynomial of $G$.
So we show $3 \nmid \chi_G(-1)$. This follows from $\chi_G(-1) \equiv \chi_G(2) = 2^c \pmod{3}$, where $c$ is the number of connected components of $G$.