ACM 2013 - Round #4Ended |
Considera una red de comunicación que consiste de un conjunto de nodos y un conjunto de pares de nodos conectados en dicha red en ambos sentidos. Es conocido que la red en cuestión es conexa, es decir, existe comunicación entre todo par de nodos. Algunos nodos proveen servicio de tipo $A$ y otros de tipo $B$ para todos los nodos en la red. Si un nodo provee algún servicio, entonces el también recibe el servicio y un nodo puede proveer los dos servicios ($A$ y $B$) al mismo tiempo. Si una conexión desaparece, puede suceder que algunos nodos en la red dejen de recibir un servicio determinado. A estas conexiones se les llama: conexiones críticas .
Tu tarea consiste en escribir un programa que determine el número de conexiones críticas y especifique cuáles son.
La primera línea de la entrada contiene cuatro enteros, $N$, $M$, $K$, y $L$. $N$ ($1 \leq N \leq 100000$) es el número de nodos de la red, $M$ ($1 \leq M \leq 1000000$) es el número de conexiones entre pares de nodos, $K$ ($1 \leq K \leq N$) es el número de nodos que proveen servicio de tipo $A$, y $L$ ($1 \leq L \leq N$) es el número de nodos que proveen servicio de tipo $B$.
Los nodos están identificados por los números del $1$ al $N$. La segunda línea contiene $K$ enteros, los identificadores de los nodos que proveen servicio $A$. La tercera línea contiene $L$ enteros, los identificadores de los nodos que proveen servicio $B$. Cada una de las siguientes $M$ líneas contienen pares de enteros $p$ $q$ ($1 \leq p, q \leq N, p \ne q$) ,las conexiones entre los nodos. Existe como máximo una conexión entre dos nodos.
La primera línea de la salida contiene un entero $S$, el número de conexiones críticas. Cada una de las siguientes $S$ líneas contienen dos enteros cada una $p$ y $q$ describiendo las conexiones críticas (en cualquier orden).