19036번 - Hokusai Artworks 다국어

문제

There are $N$ cities on some Japanese island and $M$ one-directional roads connecting those cities. Each city has a museum which is open at even days and is closed at odd days. Museum of $i$-th city holds $w_i$ Hokusai artworks.

Bytika arrived on the main city of the island (whis is placed at city 0) at the morning of an even day. Each day, she visits the museum in the current city (if the museum is open on that day and if she did not visit this museum before), and moves overnight to another city (possibly one she already visited) by using any one road leading from the current city. If Bytika cannot leave the current city, or if here are no chances to see new Hokusai artworks, she leaves the island by plane.

Find the maximum number of Hokusai artworks Bytika can see.

입력

The first line of input contains two integers $n$ and $m$ (1ドル \le n \le 10^5,ドル 0ドル \le m \le \min (n \cdot (n - 1), 10^5)$): the number of cities and the number of roads. The second line contains $n$ integers $w_0,ドル $w_1,ドル $\ldots,ドル $w_{n - 1}$; $i$-th of those integers is the number of Hokusai artworks in the museum of $i$-th city (0ドル \le w_i \le 1000$). Each of next $m$ lines contains two integers $s_j$ and $t_j$ denoting that there is a one-directional road from city $s_j$ to city $t_j$ (0ドル \le s_j, t_j \le n - 1,ドル $s_j \ne t_j,ドル $(s_j, t_j) \ne (s_i, t_i)$ if $i \ne j$).

출력

Print one integer: the maximum number of distinct Hokusai artworks Bytika can see while traveling on the island.

제한

힌트