Dominos 2

Interview

Time limit1sMemory limit128 MB

Summary
Given directed edges between dominos and a set of manually pushed dominos, count how many dominos end up falling.
Level

Medium4 of 10

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

Problem

Dominos are lots of fun. Children like to stand the tiles on their sides in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line. Sometimes, though, a domino fails to knock the next one over, and it must be knocked down by hand to keep the chain going.

Given a set of dominos that are knocked down by hand, determine the total number of dominos that fall.

The dominos form a directed structure: some dominos, when they fall, cause specific other dominos to fall. A domino falls if it is knocked down by hand, or if some domino that has fallen causes it to fall (directly or through a chain). Count all of the dominos that end up fallen.

Input

The first line contains an integer TT, the number of test cases. Each test case begins with a line containing three integers nn, mm, ll, each no larger than 1000010000, followed by m+lm + l additional lines. Here nn is the number of dominos, numbered from 11 to nn. Each of the next mm lines contains two integers xx and yy, meaning that if domino xx falls it also causes domino yy to fall. Each of the following ll lines contains a single integer zz, meaning domino zz is knocked over by hand.

Output

For each test case, output a single line containing one integer: the total number of dominos that fall.

Examples2

  1. Example 1

    Input
    1
    3 2 1
    1 2
    2 3
    2
    
    Expected output
    2
    
  2. Example 2

    Input
    1
    3 2 1
    1 2
    2 3
    1
    
    Expected output
    3