34102번 - 월향 방탈출 투 스텝

문제

이 문제는 투 스텝 문제입니다.

월간 향유회는 사업을 확장하기 위해 방탈출 카페를 만들었다. 카페에는 PS를 소재로 하는 월향 방탈출이라는 테마가 있는데, 평소 PS와 방탈출을 모두 좋아하던 도훈이와 준혁이는 함께 월향 방탈출 테마를 공략해보기로 했다. 방을 탈출하기 위한 미션은 다음과 같다.

• 월향 방탈출 테마는 두 개의 방 A와 B로 이루어져 있다. 도훈이와 준혁이는 각자 방 A와 방 B에 들어간다.
• 방 A에는 빨강, 파랑, 초록 색연필과 최대 10자리의 정수 비밀번호가 적힌 쪽지, 그리고 그래프 하나가 놓여있다. 주어지는 그래프는 아래의 명세를 모두 만족하며, 그래프의 간선은 모두 색칠되지 않은 상태이다.
• 도훈이는 방 A에 놓인 그래프의 모든 간선을 세 가지 색 중 원하는 색으로 색칠한 뒤 제출한다.
• 제출한 그래프는 방 B에 있는 준혁이에게 전달된다.
• 준혁이는 전달받은 그래프를 보고서 도훈이에게 주어진 비밀번호를 유추해서 맞혀야 한다.

방 A에 제공될 그래프의 명세는 다음과 같다.

• 정점이 100ドル$개다.
• 간선에 방향성이 없다.
• 중복된 간선이 없다.
• 간선이 잇는 두 정점은 서로 다르다.
• 간선이 2ドル,000円$개 이하다.
• 모든 정점의 차수는 20ドル$ 이상이다.

도훈이와 준혁이는 지금까지 방탈출에 실패해 본 적이 없다. 이 기록이 깨지지 않도록 도훈이는 그래프의 간선을 잘 색칠해야 하고, 준혁이는 그래프를 보고 비밀번호를 잘 맞혀야 한다.

입력

당신의 프로그램은 채점 데이터 하나당 총 두 번 실행된다. 당신은 하나의 소스코드에 두 가지 실행 과정을 모두 구현해야 한다.

모든 입력의 첫 줄에는 방을 구분하는 문자열 $S$가 주어진다. $(S \in \{ $A,ドル $B$\})$

만약 $S$가 A라면 첫 번째 단계를 수행해야 하고, $S$가 B라면 두 번째 단계를 수행해야 한다.

출력

제한

첫 번째 단계

입력

둘째 줄에 비밀번호를 나타내는 정수 $P$가 주어진다. $(0\le P< 10^{10})$

셋째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. $(N=100,$ $M \le 2,000円)$

이어서 $M$개의 각 줄에는 그래프의 $i$번째 간선이 잇는 두 정점 $u_i,ドル $v_i$가 공백으로 구분되어 주어진다.

출력

길이 $M$의 R, G, B로만 이루어진 문자열을 출력한다. R은 빨간색, G는 초록색, B는 파란색을 의미하며 $i$번째 문자는 $i$번째 간선의 색을 의미한다.

두 번째 단계

입력

채점 프로그램은 첫 번째 단계의 그래프 정점 번호를 섞고, 그래프 간선 순서와 출력 문자열을 동일한 순서로 섞은 뒤 두 번째 단계의 입력으로 제공한다.

둘째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 공백으로 구분되어 주어진다. $(N=100,$ $M \le 2,000円)$

셋째 줄에는 간선들의 색을 나타내는 길이 $M$의 R, G, B로만 이루어진 문자열이 주어진다.

이어서 $M$개의 각 줄에는 그래프의 $i$번째 간선이 잇는 두 정점 $u_i,$ $v_i$가 공백으로 구분되어 주어진다.

출력

찾아낸 비밀번호를 출력한다.

힌트