SP9124 GCPC11H - Sightseeing

作为一名喜欢户外活动的计算机科学专业学生，你决定去徒步旅行。今年的假期，你找到了一座岛屿，上面有许多适合游览的美丽地方。你已经确定了一些非常有潜力的路线，但由于选择过多，你只能选择最多 $10^5$ 个景点。 除此之外，你对参观景点的顺序也非常挑剔，所以你已经决定好要按某个顺序参观这些预选的路线。现在的问题是，需要确定每条路线的行进方向，甚至可能要进一步减少选择。在你知道不同路线的两个终点间旅行所需时间后，你决定编写一个程序，以判断是否可以在计划的时间内完成所有旅行。因为你不想浪费宝贵的时间，你只关注最优解。此外，这些路线可能会很有挑战性，所以你不愿意在同一条路线上走两次。

输入的第一行包含一个整数 $C$，表示测试用例的数量 ($0 < C$)。每个测试用例的第一行包含两个整数 $N$ 和 $T$，分别表示路线的数量 ($1 \le N \le 10^5$) 和整个假期可用的最长徒步旅行时间 ($0 \le T \le 10^6$)。紧接着的 $N$ 行中，每行包含五个整数 $c_p, c_{bb}, c_{be}, c_{eb}$ 和 $c_{ee}$，用于描述路线（按重要性排序）。$c_p$ 表示路线的长度（分钟）。$c_{xy}$ 表示从该路线的起点或终点到下一条更重要路线的起点或终点的旅行时间，其中 $x$ 和 $y$ 分别表示起点或终点。以上所有值均为不超过 $10^6$ 的非负整数。由于你需要返回到车的位置，路线是环形的。此外，我们将忽略你开车到起点的时间。

对于每个测试用例，输出一行。输出应包含一个由 **F** 和 **B** 组成的序列，指示每条路线你应该向前还是向后走（按顺序排列）。如果无法在计划时间 $T$ 内完成所有旅行，则输出 **IMPOSSIBLE**，表示这些旅行超出了你的能力范围。您可以假设最优解是唯一的。 **本翻译由 AI 自动生成**