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   v (con u ≠ v) denotando que hay una conexión directa de u a v. Asumid 0 ≤ n ≤ 10000, 0 ≤ c ≤ n, y 0 ≤ m ≤ 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.