Longest Chain of Loop Clubs

Difficulty: 2100 4000 ms 128 MB

dp graphs scc

A path may revisit nodes and edges. Print the maximum number of DISTINCT nodes visitable by a single (arbitrarily long) walk in the directed graph.

Input: the first line has N and M; each of the next M lines has a directed edge u → v.

Output: the maximum number of distinct nodes on one walk.

Constraints:

• 1 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴

Sample Tests

5 5
1 2
2 3
3 1
3 4
4 5

5

3 1
1 2

2

Read the Editorial