| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 233 | 62 | 27 | 16.168% |
현대모비스는 자율주행, 인포테인먼트, 전동화 등 미래차 핵심 기술을 선도하는 글로벌 6위의 자동차 부품 기업이다. 현대모비스는 전통적인 하드웨어 중심의 자동차 부품 회사에서 소프트웨어(SW) 중심의 기술 기업으로 거듭나기 위해 연구개발 역량을 강화하고 있다.
특히 센서와 로직 등 자율주행에 특화된 융합 소프트웨어 분야 개발에 박차를 가하고 있으며, 빅데이터/인공지능을 연구개발에 적극 활용하고 있다. 앞으로도 현대모비스는 그동안 축적해 온 하드웨어 역량과 소프트웨어 기술의 시너지를 글로벌 시장으로 확대해 나갈 예정이다.
현대모비스의 자율 주행 시험장은 $N$개의 거점으로 구성되어 있다. 1ドル$번 거점이 출발지이며, 각 거점에는 왼쪽과 오른쪽의 두 방향으로 이루어진 갈림길이 있다. 각 갈림길에는 도로가 연결되었을 수도, 아닐 수도 있다. 도로가 연결된 경우 이 도로를 통해 다른 거점으로 이동할 수 있다. 도로의 개수는 정확히 $N-1$개이며 1ドル$번 거점에서 출발해서 다른 모든 거점에 도달할 수 있다. 즉, 자율 주행 시험장은 1ドル$번 거점을 루트로 하는 이진 트리 형태이다.
당신의 목표는 $A$번 거점에 있는 자동차를 $B$번 거점으로 이동시키기 위한 프로그램을 작성하는 것이다. 프로그램은 다음과 같은 세 개의 명령어로 구성된다.
L (좌회전): 자동차가 현재 거점의 왼쪽 갈림길에 연결된 도로를 통해 이동한다. 왼쪽 갈림길에 연결된 도로가 없을 경우 에러를 일으킨다.R (우회전): 자동차가 현재 거점의 오른쪽 갈림길에 연결된 도로를 통해 이동한다. 오른쪽 갈림길에 연결된 도로가 없을 경우 에러를 일으킨다.B (후진): 자동차가 후진해 1ドル$번 거점과 가까운 방향으로 연결된 도로를 통해 이동한다. 현재 1ドル$번 거점에 위치해 있을 경우 에러를 일으킨다.단, 제어 시스템이 망가져 입력된 프로그램을 두 번 실행하게 되었다. 즉, 입력된 프로그램이 LRB라면 LRBLRB를 대신 실행한다.
두 번 실행하는 동안 에러가 발생하지 않으면서 $A$번 거점에 있는 자동차를 $B$번 거점으로 이동시키는 프로그램이 존재하는지 판별하고, 존재한다면 가장 짧은 프로그램을 구하여라.
첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. (1ドル \le T \le 200,000円$)
각 테스트 케이스의 첫째 줄에는 거점의 수 $N$이 주어진다. (2ドル \le N \le 200,000円$)
각 테스트 케이스의 둘째 줄에는 시작 거점과 도착 거점의 번호를 의미하는 두 정수 $A,ドル $B$가 공백으로 구분되어 주어진다. (1ドル \le A, B \le N;\ A \neq B$)
각 테스트 케이스의 셋째 줄부터 $N$개의 줄에 걸쳐 두 정수 $L_i,ドル $R_i$가 공백으로 구분되어 주어진다.
$L_i$는 $i$번 거점의 왼쪽 갈림길에 도로가 연결되어 있다면 도로에 연결된 거점의 번호, 그렇지 않다면 0ドル$이다. $R_i$는 $i$번 거점의 오른쪽 갈림길에 도로가 연결되어 있다면 도로에 연결된 거점의 번호, 그렇지 않다면 0ドル$이다.
주어진 구조가 1ドル$번 거점을 루트로 하는 트리 형태임이 보장된다.
모든 테스트 케이스에 대해 $N$의 합은 1ドル,000円,000円$ 이하이다.
각 테스트 케이스에 대한 답을 $T$개의 줄에 걸쳐 순서대로 출력한다.
각 테스트 케이스에 대해, 조건을 만족하는 프로그램이 존재한다면 그중 가장 짧은 프로그램을 출력한다. 이때 가장 짧은 프로그램이 여러 개일 경우 그중 아무 것이나 출력한다. 만약 조건을 만족하는 프로그램이 존재하지 않는다면 대신 ERROR를 출력한다.
2 7 7 3 2 3 4 5 6 0 7 0 0 0 0 0 0 0 7 6 2 2 3 4 5 6 0 7 0 0 0 0 0 0 0
BBR ERROR
2 12 3 6 12 7 0 9 0 0 2 0 6 8 0 0 0 0 0 11 0 0 0 4 0 3 10 5 12 1 5 12 7 0 9 0 0 2 0 6 8 0 0 0 0 0 11 0 0 0 4 0 3 10 5
BBBBLRL ERROR