Ns6 每次上冬公令的课程都会带来一堆零食。这令 Klg 和 acmp 觊觎已久。
于是，Klg 和 acmp 制定了一个秘密的劫掠计划。
机房中危机四伏。Ns6 能否逃过一劫？
机房巨大无比，结构错综复杂。其中有 个通道分叉口，有两个参数为 。讲台也属于一个分叉口，编号是 。从第 个分叉口到第 个分叉口的「NC2 距离」是 。
有 条双向的通道使得所有分叉口联通起来。换句话说，机房的结构构成了一棵以讲台为根的树。每条通道的长度是连接的两个分叉口之间的「NC2 距离」。
人只能在通道中行走，在一条通道的中间也不能拐进另一条通道。但零食可以在「NC2 距离」不大于 的两点中进行抛接传递。
Klg 和 acmp 的劫掠计划如下：
- 先选择两个分叉口 （），Klg 的起点为 ，acmp 的起点为 。记机房中连接 和 两分叉口的最短的通道形成的路径为活动路径。
- 每次，两人之间都进行一次零食传递，也就是要求每一次两人所在的分叉口之间的「NC2 距离」不超过 。请注意，初始两人在 两点时也要进行传递。
- 每次传递完零食之后，两人必须选择至少一个人向讲台的方向走恰好一条通道，然后进行下一次零食传递。但是全程两个人都不能离开活动路径。
- 某次该传递零食时，如果两人已经到了同一个分叉口，劫掠停止，计划成功。
Klg 和 acmp 共计划了 次劫掠，每次的 可能变化。现在 Ns6 需要知道的是，对于每一次劫掠计划，如果它能成功，活动路径的长度（即活动路径上每条通道的长度之和）最长会是多少？请输出这个条件下的 。如果有多解输出 最小的，还有多解输出 最小的。
请注意，本题中的两点间距离是「NC2 距离」，并非欧几里得距离。
