GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Sunday 31 July 2022

[Solution] Count Seconds Codeforces Solution


E. Count Seconds
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 ai on it.

Every second the following happens:

  • Let S be the set of nodes x that have ax>0.
  • For all xS1 is subtracted from ax, and then for each node y, such that there is an edge from x to y1 is added to ay.

Find the first moment of time when all ai become 0. Since the answer can be very large, output it

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 modulo 998244353.

Input

The first line contains a single integer t (1t1000) — the number of test cases. Description of test cases follows.

The first line of each test case contains two integers n,m (1n,m1000) — the number of vertices and edges in the graph.

The second line of each test case contains n integers a1,a2,,an (0ai109) — the integer on vertices.

Each line of the following m lines contains two integers x,y (1x,yn), represent a directed edge from x to y. It is guaranteed that the graph is a DAG with no multi-edges, and there is exactly one node that has no out edges.

It is guaranteed that both sum of n and sum of m over all test cases are less than or equal to 10000.

Output

For each test case, print an integer in a separate line — the first moment of time when all ai become 0, modulo 998244353.

No comments:

Post a Comment