12843번 - 복수전공

문제

영준이는 소프트웨어 학부 학생이다. 하지만 컴퓨터 학부에 듣고 싶은 강의가 많아 복수 전공을 하게 되었다.

소프트웨어 학부와 컴퓨터 학부는 커리큘럼이 대부분 비슷하기 때문에, 두 학부의 강의의 내용이 겹치는 경우가 발생했다. 그래서 한 학부의 수업이 다른 학부의 여러 수업을 포함하는 경우도 있다.

영준이는 최대한 많은 양의 수업을 듣고 싶다. 그리고 강의의 내용이 겹치지 않게 수강을 할 것이다. 강의의 정보와 강의 내용 간에 중복이 발생하는 관계가 주어 졌을 때 최대로 수강할 수 있는 강의의 개수를 구해주자.

입력

강의의 개수 n (1 ≤ n ≤ 2,000) 과 수업 간 관계의 개수 m (1 ≤ m ≤ 1,000,000) 이 첫 줄에 주어진다.

다음 n 줄에 대하여 강의의 번호와 어느 학부의 강의인지 알려준다. 강의의 번호는 1부터 N으로 주어진다. 컴퓨터 학부의 강의는 'c', 소프트웨어 학부의 강의는 's'로 표시된다.

다음 m 줄에 대하여 두 학부 간의 강의 중 겹치는 내용이 존재한 관계 번호들이 주어진다. 동일한 두 강의의 관계가 중복해서 나오지 않는다.

출력

영준이가 최대로 수강 할 수 있는 강의의 수를 출력하자

제한

힌트