ACM 2013 - Round #4Ended |
Un grupo de turistas tienen la oportunidad de visitar algunas ciudades en una excursión por toda Cuba. Cada turista tiene exactamente dos deseo. Un deseo de un turista dicta si quiere o no visitar una ciudad determinada. Es permitido que un turista quiera y no quiera visitar una ciudad simultáneamente. Tu tarea es escribir un programa que lea la descripción de los deseos de cada turista y determine si es posible determinar un plan de visitas a ciudades tal que a cada turista se le cumpla al menos un deseo o determine que es imposible tal plan.
La primera línea de la entrada contiene dos enteros positivos $N$ y $M$ $(1 \leq N \leq 20000, 1 \leq M \leq 8000)$; $N$ es el número de turistas y $M$ es el número de ciudades. Los turistas están numerados de $1$ a $N$, y las ciudades de $1$ a $M$. Cada una de las siguientes $N$ líneas contiene dos números $a_i$ y $b_i$ $(1 \leq |a_i|, |b_i| \leq M)$ que representan los dos deseos del i-ésimo turista. Si un deseo es positivo significa que el turista desea visitar la ciudad con ese número, y si es negativo, no desea visitar la ciudad.
El programa debe escribir en la primera línea un entero no negativo $L$, el número de ciudades en el plan de visitas. En la segunda línea $L$ enteros positivos separados por espacio representando las ciudades visitadas. Si es imposible obtener tal lista, tu programa debe imprimir “NO” sin comillas. En caso de múltiples soluciones, imprima cualquiera de ellas.
Otra posible solución:
2
1 2