Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0208 - SPY NETWORK

The NSA has found a way to factor large integers! They are using it to send encrypted messages over their spy networks. Their spy network can be modelled as a directed graph G = (V, E), where vertices are agents of the NSA and an edge from u to v models that u can inconspicuously tell its information to v (’v is a contact of u’). Note that v might not be able to send information back to u!

The NSA is constantly looking out for signs of various known terrorist organisations. Ev- ery few months its agents report to their colleagues what organisations they have heard ru- mours about during their surveillance. The protocol for this is as follows. On the specified date, all agents will send the information they have gathered to their contacts. If an agent receives information ireceived from any source, it looks at the information iold it has found so far, and generates from this a new report inew , in which it stores data on terrorist organisa- tions that were present in both ireceived and iold (this is because the NSA gets too many false alerts, so they believe a message if ALL sources agree on something). The agent then stores inew as the new ‘data it currently knows about’, and then sends this information to all its own contacts, who then act in the same manner, and so on. After a while, agents only receive messages that do not change their stored data. At the end of the day, agents stop sending messages, which is always enough for the aforementioned state to be reached. Note that the graph may not be connected and that it may contain cycles for redundancy.

The NSA uses the following encryption for this protocol. For every large terrorist organi- sation, they pick a large prime number and they distribute this mapping to all their agents. If a member generates his report, he multiplies the large prime numbers that correspond to the organisations he has heard about, and then the resulting number will be his ‘report’ that he sends to his contacts. When an agent receives ireceived, he takes the greatest common divisor of ireceived and iold. The resulting number is precisely the number you would get if you multi- ply the large prime numbers corresponding to the terrorist organisations that both members of the NSA that generated the reports have heard rumours about, and so exactly forms inew . If an agent is important enough, he gets access to the factoring algorithm and is able to read the messages sent by his contacts. Most agents just propagate the messages though, and using the greatest common divisor algorithm, they can do so without having to factor the number.

 The NSA has recently learned that an encrypted report that was generated after such a day has been leaked! Although the message was encrypted and so no information was lost, the NSA still wants to know which of its members has leaked the message and has asked for your help. Of course, you must write a pro- gram to do the work for them - you are not allowed to know the data yourself. Your program will get the structure of their spy network, along with the initial reports for every member and the leaked report. You are to print out the number of members that had this leaked report as a final report, so that the NSA knows how far they can narrow down their investigation.

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:

  • one line with three space-separated integers n, m and l (1 n 10 000 and 0 m

10 000 and 1 l < 263): the number of agents, contact edges and the leaked report.

  • m lines, each with two space-separated integers a and b (1 a, b n and a ƒ= b), indicating that agent b is a contact of agent a.

  • n lines, each with a single integer i (1 i < 263): the initial information of each agent.

Output

Per test case:

  • one line with a single integer: the number of agents with l as its stored message at the end of the message sending day.

Examples

stdin

stdout

1

3
4 3 7
1 3
2 3
3 4
35
77
385
385
4 4 159
1 2
2 3
3 1
4 1
159
159
159
2014
5 5 9
2 1
2 3
3 2
3 4
5 4
27
54
90
315
135

2
0
2


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Benelux Preliminary (BAPC) 2014.G

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.