CF1704E Count Seconds

Cirno has a DAG (Directed Acyclic Graph) with $ n $ nodes and $ m $ edges. The graph has exactly one node that has no out edges. The $ i $ -th node has an integer $ a_i $ on it. Every second the following happens: - Let $ S $ be the set of nodes $ x $ that have $ a_x > 0 $ . - For all $ x \in S $ , $ 1 $ is subtracted from $ a_x $ , and then for each node $ y $ , such that there is an edge from $ x $ to $ y $ , $ 1 $ is added to $ a_y $ . Find the first moment of time when all $ a_i $ become $ 0 $ . Since the answer can be very large, output it modulo $ 998\,244\,353 $ .

N/A

N/A

In the first test case: - At time $ 0 $ , the values of the nodes are $ [1, 1, 1] $ . - At time $ 1 $ , the values of the nodes are $ [0, 1, 1] $ . - At time $ 2 $ , the values of the nodes are $ [0, 0, 1] $ . - At time $ 3 $ , the values of the nodes are $ [0, 0, 0] $ . So the answer is $ 3 $ . In the second test case: - At time $ 0 $ , the values of the nodes are $ [1, 0, 0, 0, 0] $ . - At time $ 1 $ , the values of the nodes are $ [0, 1, 0, 0, 1] $ . - At time $ 2 $ , the values of the nodes are $ [0, 0, 1, 0, 0] $ . - At time $ 3 $ , the values of the nodes are $ [0, 0, 0, 1, 0] $ . - At time $ 4 $ , the values of the nodes are $ [0, 0, 0, 0, 1] $ . - At time $ 5 $ , the values of the nodes are $ [0, 0, 0, 0, 0] $ . So the answer is $ 5 $ .In the third test case: The first moment of time when all $ a_i $ become $ 0 $ is $ 6\cdot 998244353 + 4 $ .