Hi please could you someone help me with this python question. Part of my uni course!!! Only have an hour till submission and totally lost. Thank you so much! Any help at this point would be appreciated.

TASK

A virus is spreading across the Island of Occavia. Computer Scientists can help. You have been asked to advise the government.

Virus testers have been instructed to identify all infected people. Virus testers could obviously be placed all over the island, but there is a shortage of virus testers.

The island can be seen as a rectangular grid of squares. Each square is a county. If you place a virus tester in a county you can be certain that all infected people will be identified.

It is expected that people will migrate across the island when they realise the need for testing. You know that infected people will move from county to county to county...

You have data from a study that involved going through the entire island to see which direction people will move from each county. This information does not tell you where the infected people are, but it does tell you how they will move through Occavia.

Task:
Write a program that determines what the minimum number of virus testers is that you should place to ensure that you will identify all infected people, no matter where they currently are.

Input:
On the first line of the input are two integers n and m, separated by a space.
n and m are greater than 0 and less than 1001. These integers indicate the size of the island.
On the next n lines you will find m characters ('N','S','E','W') that indicate in what direction an infected person in a county will go once the movement of people starts.
No infected person will ever walk off the island.

Output:
Write one number that indicates what the minimum number of virus testers is that you need to ensure that you will be able to identify every infected person.

Example Input:

3 4
SWWW
SEWN
EEEN

Example output:

2

How this is graded:
For small islands, where n and m range from 1 to 5, there are 4 marks available. To get the full 10 marks your program will need to be able solve the problem, in a reasonably short amount of processing time, for islands where n and m range from 100 to 1000.