Statement

RANDy is back at it again, but now he is ready to showcase his elite dog training skills. He's been training his dog Pompieru for many years, and now he is ready to participate in a dog trick competition. There are K + 1 tricks which can be performed in this competition, numbered from 1 to K + 1. Pompieru does not know how to perform the trick K+1, so he can only perform the tricks from 1 to K. Moreover, performing specific tricks one after the other is not always possible: he can only perform trick b right after trick a if he has been trained to do so. RANDy trained Pompieru to perform M pairs of consecutive tricks (A_i, B_i), meaning that Pompieru knows how to perform trick B_i right after trick A_i. The participants are required to perform N tricks T_0, T_1, …, T_N-1 in this specific order. For each successfully performed trick the dog gets 1 point. A dog may decide to skip a trick and continue with the next trick instead...