Longest Increasing Path in a Directed Acyclic Graph

Given a directed acyclic graph (DAG) with (n) vertices and (m) edges, where each vertex is assigned a distinct integer value, find the longest path such that the values of the vertices in the path are strictly increasing. A valid path must contain at least two vertices. If no such path exists, output 0 and an empty path.

More formally, if the vertices are numbered from 1 to (n) and the value of vertex (i) is (a_i), and an edge from (u) to (v) exists if there is a directed edge from vertex (u) to vertex (v), you are to determine a sequence of vertices (p_1, p_2, \dots, p_k) (with (k \ge 2)) such that for each consecutive edge (p_i \rightarrow p_{i+1}) in the graph, the condition (a_{p_i} < a_{p_{i+1}}) holds and (k) is maximized. If there are multiple solutions, any one is acceptable.

The problem can be approached using topological sorting (via Kahn's algorithm) combined with dynamic programming to track the longest strictly increasing path ending at each vertex. Use predecessor tracking to reconstruct the path.

inputFormat

The input is read from standard input and has the following format:

• The first line contains two integers (n) and (m), representing the number of vertices and edges respectively.
  
• The second line contains (n) space-separated integers, representing the distinct values assigned to the vertices (in order from vertex 1 to vertex (n)).
  
• The following (m) lines each contain two space-separated integers (u) and (v), indicating a directed edge from vertex (u) to vertex (v>.

outputFormat

The output is written to standard output. If there is a valid strictly increasing path of at least two vertices, the first line should contain the length (k) (the number of vertices in the path) and the second line should list the sequence of vertex indices (1-indexed) that form the longest increasing path, separated by spaces. If no such path exists, output a single line containing 0.## sample

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

3
2 3 5