Hành Trình Qua Các Mốc · canuc80k3209

Có $n$ mốc được đánh số từ $1$ đến $n$ và $m$ lối đi một chiều. Mỗi lối đi $u \to v$ cho phép đi trực tiếp từ mốc $u$ sang mốc $v$ .

Hệ thống lối đi không chứa chu trình có hướng: không thể bắt đầu ở một mốc, đi qua ít nhất một lối đi rồi quay lại chính mốc đó.

Một hành trình có hướng là một dãy mốc liên tiếp sao cho giữa hai mốc kề nhau luôn có lối đi đúng chiều. Độ dài hành trình là số lối đi đã sử dụng, không phải số mốc xuất hiện trong hành trình.

Hãy tìm độ dài lớn nhất của một hành trình có hướng bất kỳ. Hành trình được phép bắt đầu và kết thúc tại bất kỳ mốc nào.

Input

Dòng đầu chứa hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ , mô tả một lối đi một chiều $u \to v$ .

Output

In một số nguyên: số lối đi lớn nhất có thể xuất hiện trong một hành trình có hướng.

Constraints

$2 \leq n \leq 1 0^{5}$ .
$1 \leq m \leq 1 0^{5}$ .
$1 \leq u, v \leq n$ .
Các cặp $(u, v)$ đôi một khác nhau.
Đồ thị không chứa chu trình có hướng.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 10$ và $m \leq 30$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Có thể đi theo hành trình $1 \to 3 \to 5 \to 6$ , sử dụng $3$ lối đi. Không có hành trình nào dùng nhiều hơn, nên kết quả là $3$ .

Test 2

Input

Output

Giải thích: Đồ thị có nhiều thành phần rời nhau. Hành trình $4 \to 5 \to 6 \to 7$ dùng $3$ lối đi, dài hơn hành trình $1 \to 2$ , nên kết quả là $3$ .

Ý tưởng: Đặt dp[v] là số cạnh lớn nhất của một đường đi có hướng kết thúc tại đỉnh v. Một đường đi chỉ gồm riêng v có độ dài 0, nên ban đầu mọi dp[v] = 0.
Ý tưởng: Ta sắp các đỉnh theo thứ tự topo bằng thuật toán Kahn. Khi lấy đỉnh u ra khỏi hàng đợi, mọi đỉnh có cạnh đi vào u đã được xử lý. Với mỗi cạnh u → v, nối cạnh này vào đường đi tốt nhất kết thúc tại u và cập nhật
Ý tưởng:

text dp[v] = max(dp[v], dp[u] + 1). - Ý tưởng: Đáp án là giá trị lớn nhất trong toàn bộ mảng dp. - Tính đúng đắn: Bổ đề 1. Khi một đỉnh u được lấy ra theo thứ tự topo, dp[u] bằng độ dài lớn nhất của mọi đường đi kết thúc tại u. - Tính đúng đắn: Chứng minh. Mọi đường đi không rỗng kết thúc tại u có cạnh cuối x → u. Do x đứng trước u trong thứ tự topo, giá trị đúng của dp[x] đã được dùng để cập nhật dp[u]. Thuật toán lấy lớn nhất trên mọi cạnh đi vào, nên không bỏ sót đường đi nào và cũng chỉ tạo các đường đi hợp lệ. ∎ - Tính đúng đắn: Bổ đề 2. Sau khi xử lý cạnh u → v, giá trị dp[v] xét đầy đủ mọi đường đi có cạnh cuối là u → v. - Tính đúng đắn: Chứng minh. Bỏ cạnh cuối khỏi một đường đi như vậy ta thu được một đường đi kết thúc tại u; đường tốt nhất trong nhóm có độ dài dp[u] + 1, đúng bằng ứng viên được cập nhật. ∎ - Tính đúng đắn: Định lý. Thuật toán in độ dài đường đi có hướng dài nhất trong đồ thị. - Tính đúng đắn: Chứng minh. Theo Bổ đề 1, sau khi duyệt topo, mỗi dp[v] là độ dài lớn nhất của đường đi kết thúc tại v. Mọi đường đi kết thúc tại một đỉnh nào đó, nên giá trị lớn nhất của các dp[v] chính là đáp án toàn đồ thị. ∎ - Độ phức tạp: Mỗi đỉnh và mỗi cạnh được xử lý hằng số lần, nên thời gian là O(n + m) và bộ nhớ là O(n + m).