Informatica Online Judge

  동굴 비상 탈출로 [1700 / 06A4]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 3   Total Tried : 3


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (33rd 박준영)]

Background

수학 퍼즐을 좋아하는 경곽이는 도서관에서 "창의 수학 퍼즐 1000"이라는 책을 보다가 재밌는 문제를 발견했다.



각 동굴에서 갈 수 있는 길은 빨간 길과 파란 길 두가지가 있다. 어떤 정해진 순서대로 길을 따라가면
어느 동굴에서 출발했는지에 관계없이 항상 같은 동굴에 도착하게 된다.

마침 동굴 관광 사업을 계획하던 경곽이는 이 아이디어를 비상 탈출로를 만드는데 사용하기로 했다.
복잡하게 생긴 동굴 어디에서든 정해진 순서대로만 따라가면 밖으로 나갈 수 있기에
동굴 여기저기에 지도를 붙일 비용을 아낄 수 있기 때문이다.

돈을 벌 생각에 너무 신이 난 경곽이는 빨간 길과 파란 길 스티커를 아무렇게나 붙이는 만행을 저질렀다.

당신은 탈출로를 어떻게 만들어야 할지 모르는 경곽이를 도와주고 사업 수입금을 나눠가지기로 하였다.

동굴의 구조가 주어졌을 때 출구를 만들어야 할 동굴과 탈출로의 길이, 탈출 순서를 구하자.

Input

첫째줄에 동굴의 갯수 $n$이 주어진다.
둘째줄의 $i$번째 수는 $i$번 동굴에서 빨간 길을 따라 갔을때 나오는 동굴의 번호이고,
셋째줄의 $i$번째 수는 $i$번 동굴에서 파란 길을 따라 갔을때 나오는 동굴의 번호이다.
빨간 길이나 파란 길이 자기 자신으로 연결된 동굴은 없다.

[입력값의 정의역]

$3<=n<=20$

Output

첫째줄에 탈출로를 따라 갔을때 도착하는 동굴의 번호와 탈출로의 길이를 출력한다.
둘째줄에 탈출 순서를 출력한다. 빨간 길은 R, 파란 길은 B로 나타내며 길이가 같은 순서가 여러개 있으면 사전순으로 먼저 오는 것을 출력한다.
만약 한 동굴로 모이는 탈출 순서가 없다면 ERROR를 출력한다.

IO Example

입력1
5
2 3 4 1 1
3 4 5 5 2

출력1
1 6
BBRRBR

설명
위 그림의 입력이다.



출발점에 상관 없이 파랑, 파랑, 빨강, 빨강, 파랑, 빨강 길을 따라가면 1번 동굴에서 끝난다.

입력2
3
2 3 1
3 3 1

출력2
3 3
BRB

입력3
3
2 3 1
3 1 2

출력3
ERROR

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]