Statement

After seven years Edoardo and Luca have reunited for their favorite activity: visiting pet fairs. The pet fair they're visiting today has N exhibitions, each of which can be either a dog or a cat exhibition. The exhibitions are connected by M one-directional roads, the i-th of which goes from exhibition X_i to exhibition Y_i. Luca, being a strong supporter of dogs, decides to play a game with Edoardo. They will enter the fair at a starting exhbition, then as long as it is possible the following happens: (1) If Luca and Edoardo are at a dog exhibition, Luca will choose the next exhibition to attend among those connected to their current one through a single road; (2) If they are at a cat exhibtion, Edoardo will choose among the same set of exhibitions. If Edoardo and Luca find themselves without the possibility to move to a different exhibition the game ends. Notice that this game might never end...