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 \enspace v$ (with $u \ne v$) denoting that there is a direct connection from $u$ to $v$. Assume $0 \le n \le 10000$, $0 \le c \le n$, and $0 \le m \le 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.