Carlsdale Caverns

Many thanks to Clive Fraser for creating this problem!

Carlsdale Caverns is a limestone area with a substantial cave system below the ground. The system consists of a large number of spectacular caverns, connected by narrow caves. Some of the caverns can be entered via a cave running from the surface. These caves provide entrances and exits for the system of caves. Only a few of the caverns have an exit cave leading directly to the surface. No cavern has more than one direct exit cave. It is possible to travel between caverns by following the underground cave system. However, the system is not completely connected. If a pair of caverns are taken at random it may not be possible to travel from one to the other without first exiting to the surface. If it is possible to travel between the two caverns by a route which is entirely underground then there will be only one route between the two caverns. This may pass through many other caverns on the way.

Ann and Bob are keen cavers and plan to open an outdoor centre in the area, from which they will offer cave trips of varying difficulty. A cave trip will involve going into the cave system by one of the entrances and emerging by a different exit. Ann and Bob want to determine how many possible routes there are, so that they can give each one a difficulty category and brief description, so that customers can choose suitable routes. Ann and Bob also realise that they will need good maps of the intended routes. Mapping all of the caverns would take too much time. However, many of the caverns are on dead-end routes where cavers would have to retrace their path. Ann and Bob intend to use only the through routes, so they need only to map those caverns which are passed through on at least one of the through routes. They want to know how many caverns will need to be mapped.

In the cave system of N caverns, the caverns are numbered from 1 to N. The example described by the data at the end of the problem is a description of a simple cave system consisting of 17 caverns and 6 of these caverns have a direct connecting cave leading to the surface. We will label these entrances (and exits) with the same numbers as the caverns into which they emerge. In the example below the 6 entrances/exits have the numbers 6, 7, 9, 11, 13 and 16. The following table takes each entrance in turn and lists the possible exits which can be combined with it to form a route through the caverns.

6   exits 13, 16
7   exit 11
9   no exits
11  exit 7
13  exits 6, 16
16  exits 6, 13

By examining the table we can see that there are 8 different routes through the cave system. Note that the reverse of a route is counted as a different route.

If we take each of these routes in turn and list the series of caverns passed through on that route, we can accumulate a list of all of the caverns that are passed through on at least one route. For this example these are caverns 1, 2, 4, 6, 7, 11, 13, 16 and 17. So there are 9 caverns which need to be mapped. The remaining 8 caverns are all part of dead-end routes so will not be used.

The actual problem will describe a much larger cave system (so there is a substantial amount of data to be read in). The number of caverns (N) will not be greater than 2000 and the number of entrance/exit caves (E) will not be greater than 200. There will also be a large number (less than 2000) of connecting caves (C). From the data in the example below, caverns 6 and 1 have a connecting cave; caverns 10 and 14 have a connecting cave; caverns 2 and 5 have a connecting cave, and so on. You are asked to find the number of possible routes through the cave system and the number of caverns that will need to be mapped. Caverns which are not on any through route should be ignored.

Input and Answer:
The first line of the problem will contain a pair of integers, N and E, separated by a space. These are the number of caverns and the number of entrances/exits. The next (long) line will contain E space-separated integers. These are the numbers of the entrances/exits. The next line contains a single integer C for the number of connecting caves. A single (very long) line follows containing 2*C space separated integers. These are taken in pairs. Each pair gives the numbers of two caverns which have a connecting cave between them. Your answer is a pair of integers separated by a space. These are the number of routes, followed by the number of caverns to be mapped.

Example:

input:
17 6
6 11 9 7 16 13
14
6 1 10 14 2 5 3 15 1 4 11 2 13 1 2 17 3 12 16 4 3 9 8 2 10 4 7 17

answer:
8 9