빨갛게 바꾸기

시간 제한3초메모리 제한1024 MB

요약

조명의 색이 R, G, B 순서로 바뀌고 각 버튼이 여러 조명의 색을 함께 바꿀 때, 모든 조명을 빨간색으로 만드는 최소 버튼 누름 횟수를 구합니다. 불가능하면 impossible을 출력합니다.

난이도: 보통10점 중 6점
유형: 그래프, BFS, 수학
정답자: 아직 제출이 없습니다

문제

Mei의 부모님은 지난 1년 동안 집을 리모델링했지만, 조명 시스템이 꽤 복잡하다. 집의 각 방에는 LED 조명이 하나씩 있고, 그림 P.1에서 보듯 빨강, 초록, 파랑 중 하나로 설정할 수 있다.

그림 P.1: 예제 입력 1의 조명 초기 상태. 버튼과 배선은 표시하지 않았다.

집 곳곳에 여러 버튼이 있고, 각 버튼은 하나 이상의 조명과 연결되어 있다. 버튼을 누르면 그 버튼에 연결된 빨간 조명은 초록으로, 초록 조명은 파랑으로, 파란 조명은 빨강으로 바뀐다. 각 버튼은 여러 번 누를 수 있다. 이 집은 크로스바 배선이 발명되기 전에 지어졌기 때문에, 각 조명은 최대 두 개의 버튼으로 제어된다.

Mei는 모든 조명을 빨갛게 만들고 싶어 한다. 부모님은 버튼이 닳을까 걱정하며, Mei에게 버튼을 누르는 총 횟수를 최소화해 달라고 부탁했다.

입력

첫 번째 줄에 양의 정수 $l$ 과 $b$ 가 주어진다. $l$ 은 조명의 개수이고 ( $1 \le l \le 2 \cdot 10^5$ ), $b$ 는 버튼의 개수이다 ( $0 \le b \le 2 \cdot l$ ).

두 번째 줄에는 길이 $l$ 의 문자열이 주어지며, 각 문자는 R, G, B 중 하나이다. $i$ 번째 문자는 $i$ 번째 조명의 초기 색이다.

다음 $b$ 개의 줄은 버튼을 하나씩 설명한다. 각 줄은 버튼이 제어하는 조명의 개수 $k$ ( $1 \le k \le l$ )로 시작하고, 이어서 그 조명들의 서로 다른 번호 $k$ 개가 주어진다. 조명 번호는 1부터 $l$ 까지이다. 각 조명은 모든 버튼을 통틀어 최대 두 번 등장한다.

출력

모든 조명을 빨갛게 만드는 데 필요한 버튼 누르기 횟수의 최솟값을 출력한다. 불가능하면 impossible을 출력한다.

예제4

예제 1

입력

예상 출력

예제 2
입력
```
4 3
RGBR
2 1 2
2 2 3
2 3 4
```
예상 출력
```
impossible
```
예제 3
입력
```
4 4
GBRG
2 1 2
2 2 3
2 3 4
1 4
```
예상 출력
```
6
```
예제 4
입력
```
3 3
RGB
1 1
1 2
1 3
```
예상 출력
```
3
```