QOJ.ac

QOJ

Límite de tiempo: 2.5 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓

#17982. 自动驾驶程序开发

Estadísticas

现代摩比斯(Hyundai Mobis)是全球第六大汽车零部件供应商,在自动驾驶、车载信息娱乐和电气化领域处于领先地位。该公司正在加强其研发能力,以转型为一家以软件为核心的技术公司,重点关注自动驾驶软件、人工智能和大数据。通过利用其硬件专业知识和软件创新,现代摩比斯旨在加强其在全球移动出行市场中的地位。

现代摩比斯自动驾驶测试中心由 $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$。 如果第 $i$ 个检查点的左侧没有连接道路,则 $L_i$ 为 0。否则,它表示该道路通往的检查点编号。如果第 $i$ 个检查点的右侧没有连接道路,则 $R_i$ 为 0。否则,它表示该道路通往的检查点编号。

保证给定的结构是一棵以检查点 1 为根的树。

所有测试用例的 $N$ 之和不超过 $1\,000\,000$。

输出格式

对于每个测试用例,输出实现目标的最短程序。如果有多个这样的程序,输出其中任意一个。如果不存在这样的程序,输出 ERROR

样例

输入 1

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

输出 1

BBR
ERROR

输入 2

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

输出 2

BBBBLRL
ERROR

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.