El tonel de amontillado P31675

Había yo soportado hasta donde me era posible las mil ofensas de que Fortunato me hacía objeto, pero cuando se atrevió a insultarme juré que me vengaría… Continuamos nuestro camino en busca del amontillado. Pasamos bajo una hilera de arcos muy bajos, descendimos, seguimos adelante y, luego de bajar otra vez, llegamos a una profunda cripta… Puse la última piedra en su sitio y la fijé con el mortero… ¡Requiescat in pace!

Con la excusa de catar un tonel de amontillado, Montressor ha guiado al pobre Fortunato, borracho, a través de las catacumbas debajo del palacio de Montressor. Allí, en una cripta remota, Montressor ha emparedado a Fortunato en un nicho escondido. Ahora Montressor quiere retornar a la habitación en la que empezaron su ruta, pero ha olvidado el camino para llegar. Afortunadamente, tiene un mapa de las catacumbas que muestra las habitaciones y sus conexiones directas. (Tened en cuanta que algunos pasos son tan difíciles que puede ser posible pasar de una habitación $u$ a otra $v$, pero no directamente de vuelta de $v$ a $u$.) El mapa también muestra qué habitaciones tienen amontillado.

Montressor y Fortunato fueron desde una habitación inicial $x$ a otra habitación $y$ donde se encuentran ahora. Irónicamente, Montressor sabe que no hay ningún camino desde $x$ a ninguna habitación con amontillado. También sabe que es posible llegar desde $y$ de vuelta hasta $x$. Sin embargo, no es capaz de identificar cuál es $x$ ni cuál es $y$ en el mapa. Por favor, ayudadle calculando el número de combinaciones posibles para $x$ e $y$ que son consistentes con toda esta información.

Entrada

La entrada consiste en diversos casos, con el número de habitaciones $n$, un número $c$, y $c$ habitaciones diferentes con amontillado. Sigue un número $m$, y $m$ pares diferentes $u \enspace v$ (con $u \ne v$) denotando que hay una conexión directa de $u$ a $v$. Asumid $0 \le n \le 10000$, $0 \le c \le n$, y $0 \le m \le 10n$. Las habitaciones se numeran entre 0 y $n - 1$.

Salida

Para cada caso, escribid su número de caso (en inglés, “Case”), seguido del número de combinaciones para $x$ e $y$ que son consistentes con la información que tiene Montressor.