Problem D
Excavator Expedition

Photo by Markus Spiske

Little Nanouk is obsessed with excavators. In fact, he is so obsessed with them that he will throw a tantrum if he doesn’t see too many during a road trip.

This poses a problem for his mother Amka, who wants to bring him to his grandparents today. To make the drive to his grandparents as smooth as possible, she has plotted out all the construction sites they could see on their way, along with the “boring” sites (according to Nanouk). Of course, Amka also wants to make some progress for each place they drive to. For that reason, the map she has plotted out is a directed acyclic graph.

Could you help Amka find the route to their grandparents which makes Nanouk as happy as possible?

Input

First, a single line with two integers $V$ and $E$ is given. Then, a single line with $V$ characters is given, where $V_ i$ is ‘X’ if location $i$ is a construction site, and ‘.’ if it is a boring site.

Then follow $E$ lines. Every line contains two integers $F_ i$ and $T_ i$, representing that it is possible to drive from $F_ i$ to $T_ i$.

The location $0$ and $V-1$ are Amka’s home and Nanouk’s grandparents’ home, respectively.

Output

Output the happiness of Nanouk if Amka drives the route which maximises Nanouk’s happiness. Nanouk’s happiness is defined as the number of construction sites visited, minus the number of boring sites (except for Amka’s and Nanouk’s grandparents’ house).

Limits

• $1 < V \leq 400\, 000$

• $0 < E \leq 400\, 000$

• $0 \leq F_ i, T_ i < V$

• For all $0 < i < V$, $V_ i \in $ {‘.’, ‘X’}

• For $i \in \{ 0, V-1\} $, $V_ i =$ ‘.’

• There is always a path from Amka’s house to Nanouk’s grandparents.

• There are no cycles in the graph.

13 15
.X...X.X...X.
0 1
0 2
1 3
2 4
3 5
4 5
5 6
5 7
5 8
6 12
7 9
8 10
9 11
10 11
11 12

2