Vòng đua xe đạp

View as PDF
Submit solution
Points: 0.25 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
Croatian Open 2006
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một vòng đua xe đạp được tổ chức trên ~N~ thành phố, đánh số từ ~1~ đến ~N~. Có ~M~ đường nối (một chiều) giữa các thành phố. Vòng đua bắt đầu từ thành phố ~1~ và kết thúc tại thành phố ~2~.

Yêu cầu Hỏi có bao nhiêu cách tổ chức các vòng đua? (Biết hai vòng đua là khác nhau nếu chúng không sử dụng các tuyến đường như nhau)

Input

  • Dòng ~1~: ~N~, ~M~
  • ~M~ dòng tiếp theo: mỗi dòng chứa hai số nguyên ~A~, ~B~, cho biết có một đường nối giữa thành phố ~A~ và thành phố ~B~

Các thành phố có thể nối với nhau bởi nhiều hơn một con đường

Output

  • Gồm ~1~ dòng duy nhất: số cách tổ chức các vòng đua. Nếu kết qủa có nhiều hơn ~9~ chữ số, chỉ cần in ra ~9~ chữ số cuối cùng. Nếu có vô số cách tổ chức các đường đua, in ra "inf".

Giới hạn

  • ~1 \leq N \leq 10^{4}~
  • ~1 \leq M \leq 10^{5}~

Sample Input 1

8 14
6 7
6 8
7 5
5 2
5 3
4 8
1 6
5 2
7 5
6 4
1 4
5 2
7 4
8 3

Sample Output 1

6

Sample Input 2

2 2
1 2
2 1

Sample Output 2

inf

Comments

Please read the guidelines before commenting.


  • 0
    blobbyghost01  commented on Jan. 15, 2025, 12:46 a.m.

    các bạn lưu ý đề bài nói là "in 9 chữ số cuối cùng" thì phải in đủ 9 chữ số (cả các chữ số 0 ở đầu) nhé


  • -5
    VVUU  commented on Oct. 19, 2023, 3:46 a.m. ← edited

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -6
    hkbao  commented on June 6, 2023, 9:51 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      trieuyanglake_1  commented on June 6, 2023, 12:06 p.m.

      có 2 con đường từ 7 -> 5 và có 3 con đường từ 5 -> 2 , nhân vào được 6


      • -4
        hkbao  commented on June 7, 2023, 2:10 a.m.

        à ok hiểu r, do vẽ bằng grapth nên mấy cạnh trùng nó kh hiện =))


    • -5
      y  commented on June 6, 2023, 9:52 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -5
        hkbao  commented on June 6, 2023, 10:57 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


  • -11
    Minhquank25Clqd  commented on Feb. 26, 2022, 3:29 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -12
    princeoftime05  commented on July 30, 2021, 4:50 a.m. ← edit 2

    This comment is hidden due to too much negative feedback. Show it anyway.