Bicikli P47358


Statement
 

pdf   zip

thehtml

Se organiza una carrera ciclista en un país muy, muy lejano. Hay N pueblos, numerados del 1 al N, y M carreteras de sentido único que los unen. La carrera empieza en el pueblo 1 y acaba en el pueblo 2.

¿Cuántas rutas distintas es posible establecer entre ambos pueblos? Dos rutas son distintas si no usan las mismas carreteras, en el mismo orden exacto.

Entrada

La primera línea contiene dos enteros N (entre 1 y 10000) y M (entre 1 y 100000), el número de pueblos y carreteras.

Las M restantes líneas contienen dos enteros distintos A y B, representando una carretera entre el pueblo A y el B. El mismo par de pueblos puede estar conectado por más de una carretera.

Salida

Escribe una línea con el número de rutas distintas que pueden establecerse entre los pueblos 1 y 2. Si este número tiene más de 9 dígitos, escribe las últimas nueve cifras. Si hay un número infinito de rutas, escribe “inf”.

Public test cases
  • Input

    6 7
    1 3
    1 4
    3 2
    4 2
    5 6
    6 5
    3 4
    

    Output

    3
    
  • Input

    6 8
    1 3
    1 4
    3 2
    4 2
    5 6
    6 5
    3 4
    4 3
    

    Output

    inf
    
  • Input

    31 60
    1 3
    1 3
    3 4
    3 4
    4 5
    4 5
    5 6
    5 6
    6 7
    6 7
    7 8
    7 8
    8 9
    8 9
    9 10
    9 10
    10 11
    10 11
    11 12
    11 12
    12 13
    12 13
    13 14
    13 14
    14 15
    14 15
    15 16
    15 16
    16 17
    16 17
    17 18
    17 18
    18 19
    18 19
    19 20
    19 20
    
    20 21
    20 21
    21 22
    21 22
    22 23
    22 23
    23 24
    23 24
    24 25
    24 25
    25 26
    25 26
    26 27
    26 27
    27 28
    27 28
    28 29
    28 29
    29 30
    29 30
    30 31
    30 31
    31 2
    31 2
    

    Output

    073741824
    
  • Information
    Author
    COCI06/07
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++