Atcoder Educational DP Contest G - Longest Path

View as PDF
Submit solution
Points: 0.20 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout
Suggester:
takerevenge
Problem source:
Atcoder Educational DP Contest
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho đồ thị có hướng ~G~ có ~N~ đỉnh và ~M~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~N~, và cạnh có hướng thứ ~i~ ~(1 \leq i \leq M)~ đi từ đỉnh ~x_i~ tới đỉnh ~y_i~.

Đảm bảo rằng đồ thị ~G~ không có chu trình.

Tìm độ dài đường đi có hướng dài nhất trong đồ thị ~G~, quy ước rằng: độ dài của một đường đi có hướng là số cạnh nằm trên đường đi đó.

Input

  • Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~, lần lượt là số đỉnh và số cạnh của đồ thị đã cho. ~(2 \leq N \leq 10^5 , 1 \leq M \leq 10^5 ) ~

  • Dòng thứ ~i~ trong số ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i~ và ~y_i~, biểu diễn cho cạnh thứ ~i~ của đồ thị.

Đảm bảo rằng tất cả các cạnh ~(x_i, y_i)~ bất kì đều phân biệt và đồ thị ~G~ không có chu trình.

Outout

In ra độ dài của đường đi có hướng dài nhất trong đồ thị ~G~.

Sample 1

Input
4 5
1 2
1 3
3 2
2 4
3 4
Output
3
Giải thích

Đường màu đỏ trong hình dưới đây là đường đi dài nhất:

Sample 2

Input
6 3
2 3
4 5
5 6
Output
2
Giải thích

Đường màu đỏ trong hình dưới đây là đường đi dài nhất:

Sample 3

Input
5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3
Output
3
Giải thích

Đường màu đỏ trong hình dưới đây là đường đi dài nhất:

Comments

Please read the guidelines before commenting.


  • -2
    tandochuyentin2022  commented on April 12, 2024, 6:39 a.m.

    orz


  • -22
    Ducanh_ils  commented on Dec. 16, 2023, 2:56 a.m.

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


    • -11
      Ducanh_ils  commented on Jan. 3, 2024, 8:02 a.m.

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


      • -11
        Ducanh_ils  commented on Jan. 3, 2024, 8:02 a.m.

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


  • -13
    Ducanh_ils  commented on Dec. 16, 2023, 2:56 a.m.

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


    • 0
      DucNguyenNoob  commented on Jan. 3, 2024, 8:24 a.m.

      Hết cứu


    • -8
      Ducanh_ils  commented on Jan. 3, 2024, 8:03 a.m.

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


      • -12
        Ducanh_ils  commented on Jan. 3, 2024, 8:03 a.m.

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


    • 1
      nhatquang1310  commented on Jan. 1, 2024, 3:24 p.m.

      xin_loi;


      • 0
        avgnoob1  commented on Jan. 3, 2024, 9:07 a.m.

        nó bị lấy acc bl linh tinh á:))


      • -5
        Ducanh_ils  commented on Jan. 3, 2024, 8:05 a.m.

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


    • -16
      HoaBanMaTuy  commented on Dec. 16, 2023, 3:03 a.m.

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