Double Major

Yeongjun studies in the software department. Many of the courses he wants to take belong to the computer department, so he started a double major.

The two departments follow almost the same curriculum, so some courses cover overlapping material. One course in a department can overlap with several courses in the other department.

Yeongjun wants to take as many courses as possible, and he never takes two courses whose content overlaps. Given the course list and every overlapping pair, find the largest number of courses he can take.

The first line contains the number of courses $n$ ($1 \le n \le 2\,000$) and the number of overlapping relations $m$ ($1 \le m \le 1\,000\,000$).

Each of the next $n$ lines contains a course number and the department that course belongs to. Course numbers run from $1$ to $n$ and each number appears exactly once. A computer department course is marked c, and a software department course is marked s.

Each of the next $m$ lines contains the numbers of two courses whose content overlaps. The two courses belong to different departments, and the same pair of courses never appears twice.

Print the largest number of courses Yeongjun can take on one line.