Under construction

Still being built. Things may change

Drug Investigation Unit

Interview

Time limit1sMemory limit256 MB

Summary
Given a directed supply graph and a set of arrested suppliers, count how many remaining suppliers still receive drugs from some origin.
Level

Medium5 of 10

Topics
Graph, DFS, Implementation, Queue
Solved
No attempts yet

Problem

Social problems related to drugs have been occurring frequently around the world lately. In response, the police want to block drug distribution as much as the limited manpower of the drug investigation unit allows.

Drug suppliers obtain drugs from one another. The drug investigation unit has recently identified part of the network among the drug suppliers. This network can be represented as a graph. Each node is a drug supplier, and each edge represents a supply relation. For example, the graph below shows the following.

  • Drug supplier A supplies drugs to drug suppliers B, C, D, and E.
  • Drug supplier F obtains drugs from B and C, then supplies them to I.
  • I supplies J, J supplies K, D supplies G, and E supplies H.

The drug investigation unit can arrest drug suppliers whose whereabouts it has identified.

For example, even if the unit arrests B and C, D, E, G, and H can still obtain drugs.

The origin of drugs is a drug supplier that supplies drugs without obtaining any from another supplier.

Given information about the network among drug suppliers and the drug suppliers arrested by the unit, write a program that finds the number of drug suppliers that can still obtain drugs.

Input

The first line gives the number of drug suppliers N(1≤N≤26)N(1 \le N \le 26) and the number of relations among drug suppliers M(1≤M≤600)M(1 \le M \le 600). Each drug supplier is represented by an uppercase letter, starting with A in order.

From the second line, MM lines give the relations among the drug suppliers. (A B : A -> B)

The last line gives the number of drug suppliers whose whereabouts the police have identified, followed by each identified drug supplier, separated by spaces.

Output

Output the number of drug suppliers that can still obtain drugs after the drug investigation unit arrests the identified drug suppliers.

Examples1

  1. Example 1

    Input
    11 11
    A B
    A C
    A D
    A E
    B F
    C F
    D G
    E H
    F I
    I J
    J K
    2 B C
    
    Expected output
    4