SPOJ in Gyumri

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 i_received from any source, it looks at the information i_old it has found so far, and generates from this a new report i_new , in which it stores data on terrorist organisa- tions that were present in both i_received and i_old (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 i_new 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 i_received, he takes the greatest common divisor of i_received and i_old. 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 i_new . 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.

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

10 000 and 1 ≤ l < 2⁶³): 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 < 2⁶³): 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