Pequeño Viajero

Submit solution
Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
Marichal
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Cayusín es un pequeño viajero que ama explorar su país natal IslaGrande con una estructura interesante. En el país hay N pueblos conectadas por M carreteras. Cada carretera conecta dos pueblos diferentes. Se sabe que es posible ir desde cualquier pueblo a otro, quizás, visitando algunos intermedios.

El Sistema de carreteras está ordenado de tal forma que transitando a través de algunas de las carreteras, iniciando desde algún pueblo, usted puede regresar a donde inició sin visitar dos veces cualquier pueblo. La secuencia de carreteras que le permiten ir de un pueblo inicial sin visitar dos veces un mismo pueblo, se llama anillo de carreteras en IslaGrande. Es interesante que ninguno de los pueblos yace en varios anillos de carreteras a la vez.

Cayusín viene con un nuevo plan para explorar pueblos. Ahora, cada día que sale de su casa, iniciando en uno de los pueblos y va a través de una de las carreteras al pueblo vecino. Entonces selecciona una carretera y va al pueblo vecino. El principal asunto es cumplir cabalmente la condición de viaje: no ir a los pueblos que ya ha visitado. Y así él hace esto hasta llegar al pueblo de la cual todas las carreteras se dirigen a pueblos visitados. Después de esto Cayusín regresa a casa en avión.

Una vez que llega a casa, Cayusín se pregunta: ¿En cuántos pueblos diferentes pudo terminar mi recorrido? IslaGrande es un gran país, así que Cayusín no puede determinar el número de tales pueblos manualmente. Él le pide a usted, su mejor amigo, que escriba un programa que con la información de los pueblos, las carreteras y la localización de la casa de Cayusín determine el número de pueblos diferentes en los cuales Cayusín puede terminar su recorrido.

Entrada

La primera línea de entrada contiene tres enteros N, M, S (2 \leq N \leq 200\,000; N - 1 \leq M \leq \frac{4N}{3}; 1 \leq S \leq N) — el número de pueblos de IslaGrande, el número de carreteras y el número del pueblo donde está la casa de Cayusín.

Las siguientes M líneas contienen pares de enteros a_i y b_i (1 \leq a_i; b_i \leq N) — los números de los pueblos conectados por la i-ésima carretera. Se garantiza que a_i y b_i son diferentes y que dos pueblos no están conectados por más de una carretera. Los números en las líneas están separados por un espacio.

Salida

La salida debe contener un simple entero — el número de pueblos en los cuales Cayusín puede terminar su recorrido.

Ejemplos

Entrada 1
3 2 2
1 2
2 3
Salida 1
2
Explicación

Cayusín puede seleccionar la carretera que se dirige al pueblo número 1 o la carretera que se dirige al tercer pueblo. En ambos casos él se encontrará en la misma situación, cuando es posible ir solamente al 2do pueblo el cual ya ha sido visitado, o sea, su recorrido se termina.

Entrada 2
4 4 3
1 2
2 3
3 4
4 1
Salida 2
2

Comments


  • 0
    josue  commented on July 2, 2020, 8:42 p.m. ← edited

    entonces si hay pueblos q no pertenecen a ningun ciclo(cuando hay mas de uno),es q esta oracion me hizo entender mal: El Sistema de carreteras está ordenado de tal forma que transitando a través de algunas de las carreteras, iniciando desde algún pueblo, usted puede regresar a donde inició sin visitar dos veces cualquier pueblo.


  • 1
    josue  commented on June 29, 2020, 11:56 p.m.

    Supongo q en esta oración hay un error de traducción y halla q sustituir ninguno por algunos: Es interesante que ninguno de los pueblos yace en varios anillos de carreteras.Si pudieran aclararme se los agradezco.


    • 2
      aniervs  commented on June 30, 2020, 10:48 p.m. ← edited

      No, está bien. Un anillo es un ciclo simple. Te dicen que ningún nodo está en dos ciclos, es decir, que los ciclos no se intersecan.


  • 1
    alainav  commented on Jan. 8, 2020, 2:28 p.m.

    no tengo ni idea de lo q hablas


  • 2
    dmesadiaz  commented on Jan. 4, 2020, 8:55 a.m.

    Alguien podría darme una idea de como hacer este problema.