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:
Problem source:
Atcoder Educational DP Contest
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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.


There are no comments at the moment.