23052번 - 두 트리 스페셜 저지

$N$개의 정점과 서로 다른 $2(N-1)$개의 간선으로 이루어진 그래프가 주어진다. 각 정점은 $1$번부터 $N$번까지, 각 간선은 $1$번부터 $2(N-1)$번까지 번호가 부여되어 있다. $i$번 간선은 $A_i$번 정점과 $B_i$번 정점을 서로 연결한다. ($1 \le i \le 2(N-1)$)

각 간선을 빨강 혹은 파랑으로 칠하자. 빨간 간선으로 이루어진 그래프와 파란 간선으로 이루어진 그래프가 각각 트리가 되도록 간선을 칠할 수 있는지 판별하라.

첫째 줄에 정수 $N$이 주어진다. ($4 \le N \le 3\,000$)

둘째 줄부터 $2(N-1)$개의 줄에 걸쳐 그래프의 간선이 주어진다. $(i+1)$번째 줄에는 두 정수 $A_i$, $B_i$가 주어진다. ($1 \le i \le 2(N-1)$, $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$)

각 간선이 연결하는 정점쌍은 모두 다르다. ($1 \le i < j \le 2(N-1)$, $\left\{ A_i, B_i \right\} \ne \left\{ A_j, B_j \right\}$)

만일 불가능하다면 첫째 줄에 "NO"를 출력하라.

만약 가능하다면 첫째 줄에 "YES"를 출력하라. 이후 둘째 줄에 R과 B로 이루어진 길이 $2(N-1)$의 문자열을 출력하라. 이 문자열의 $i$번째 문자가 R이라는 것은 $i$번 간선을 빨강으로 칠해야 함을, B라는 것은 파랑으로 칠해야 함을 의미한다. ($1 \le i \le 2(N-1)$)

세 개의 예제를 그림으로 나타내면 아래와 같다.