«адача G

»тоги олимпиады 2005 года -> «адачи пробного тура - «адача G [page2298.html] ¬аш браузер не поддерживает JavaScript! јльтернативна€ верси€ меню без JavaScript здесь »тоги олимпиады 2005 года -> «адачи пробного тура «адача G Sum†G Taxi (1 sec) Input file: G.IN Output: Standard output On the city map where Petya Bulochkin works as taxi driver there are N squares numbered from 1 to N (each square is identified by its number). Some of the squares are connected with roads. The roads are quite narrow and the one-way traffic is assumed. From his experience Petya is aware that once one left the square there is no way back to this square. Any two roads connect different pairs of the squares. Crossroads are located only on the squares. One time Petya picked up a passenger at the square A who was willing to get to the square B . The passenger also wanted taxi to take stops at squares C 1 ... C k , where there would be some friends waiting for the passenger. The order in which the selected squares are visited is arbitrary. УHow much money should I get from the passengerФ thought Petya and decided to collect as many $ as there are different routes leading from A to B through C 1 .. C k . So the task is: given the information about city plan and squares A , B , C 1 ... C k find out the number of all possible routes from A to B trough C 1 ... C k . Input The first line of the input file contains the number of tests T . The first line of each test specifies N -Ц the number of squares and M Ц the number of roads. The next M lines contain information describing the roads. Road description line contains two numbers: the start and the end squares for the road. Be aware that itТs impossible to drive wrong way. Next line has three numbers: A Ц the start square, B Ц the end square and K Ц the number of the desired squares C 1 .. C k . The next K lines contain the numbers C 1 .. C k one per line. All the numbers A , B , C 1 .. C k Ц are different. Output . You must print to the standard output a single number S - the number of all possible routes from A to B that also have C 1 .. C k . ( S <2000 000 000 ) Input Output 1 4 4 1 2 2 3 1 4 4 3 1 3 1 2 1 Developed by Deep Vision