The cask of amontillado P31675

The thousand injuries of Fortunato I had borne as I best could; but when he ventured upon insult, I vowed revenge…We continued our route in search of the amontillado. We passed through a range of low arches, descended, passed on, and descending again, arrived at a deep crypt…
I forced the last stone into its position; I plastered it up…In pace requiescat!

With the excuse of sampling a cask of amontillado, Montressor has guided poor drunken Fortunato through the catacombs under Montressor’s palace. There, in a very remote crypt, Montressor has immured Fortunato inside a hidden niche. Now Montressor wants to return to the chamber where they started their route, but he has forgotten the way to get there. Fortunatoly, Montressor has a map of the catacombs, which shows all the chambers and their direct connections. (Note that some steps are so difficult that it may be possible to pass from one chamber u to another v, but not directly back from v to u.) The map also shows which chambers contain amontillado.

Montressor and Fortunato went from a starting chamber x to another chamber y where they are now. Ironically, Montressor knows that there is no path from x to any chamber with amontillado. Montressor also knows that it is possible to go from y back to x. However, he cannot identify which is x nor which is y in the map. Please help him by computing the number of possible combinations for x and y that are consistent with all this information.

Input

Input consists of several cases. Each one begins with the number of chambers n, a number c, and c different chambers that contain amontillado. Follows a number m, and m different pairs u   v (with u ≠ v) denoting that there is a direct connection from u to v. Assume 0 ≤ n ≤ 10000, 0 ≤ c ≤ n, and 0 ≤ m ≤ 10n. The chambers are numbered from 0 to n − 1.

Output

For every case, print its number, followed by the number of combinations for x and y that are consistent with Montressor’s knowledge.