Dominos 2
InterviewTime limit1sMemory limit128 MB
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 , the number of test cases. Each test case begins with a line containing three integers , , , each no larger than , followed by additional lines. Here is the number of dominos, numbered from to . Each of the next lines contains two integers and , meaning that if domino falls it also causes domino to fall. Each of the following lines contains a single integer , meaning domino is knocked over by hand.
Output
For each test case, output a single line containing one integer: the total number of dominos that fall.