복수전공

영준이는 소프트웨어 학부 학생이다. 컴퓨터 학부에 듣고 싶은 강의가 많아 복수전공을 시작했다.

두 학부의 커리큘럼은 대부분 비슷해서 강의 내용이 겹치는 경우가 생긴다. 한쪽 학부의 강의 하나가 다른 학부의 강의 여러 개와 내용이 겹치기도 한다.

영준이는 내용이 겹치는 두 강의를 함께 듣지 않으면서 최대한 많은 강의를 듣고 싶다. 강의 목록과 내용이 겹치는 관계가 주어질 때, 영준이가 들을 수 있는 강의 개수의 최댓값을 구하라.

첫 줄에 강의의 개수 $n$ ($1 \le n \le 2\,000$)과 내용이 겹치는 관계의 개수 $m$ ($1 \le m \le 1\,000\,000$)이 주어진다.

다음 $n$ 줄에는 강의 번호와 그 강의가 속한 학부가 주어진다. 강의 번호는 $1$부터 $n$까지이고 각 번호가 정확히 한 번씩 나온다. 컴퓨터 학부 강의는 c, 소프트웨어 학부 강의는 s로 표시한다.

다음 $m$ 줄에는 내용이 겹치는 두 강의의 번호가 주어진다. 두 강의는 서로 다른 학부에 속하고, 같은 두 강의의 관계가 두 번 이상 나오지 않는다.

영준이가 들을 수 있는 강의 개수의 최댓값을 한 줄에 출력한다.