【题目描述】
给定一个链烃，按照系统命名法给其命名。
如果你不了解什么是链烃或系统命名法，请参见提示。
【输入格式】
从文件 name.in 中读入数据。
第一行一个整数 n，表示碳原子的个数。
接下来 n − 1 行，每行两个整数 u, v 表示编号为 u 和 v 的碳原子之间由一个碳-碳单
键连接。
【输出格式】
输出到文件 name.out 中。
第一行输出三个数，分别表示主链的长度 l，主链的两个端点 u, v。主链可能不唯一，
任意输出一个合法的即可，详见提示。
接下来 n 行，第 i 行先输出一个 ki ，表示命名结果中 i− 烷基的数量。接着升序输
出每个 i− 烷基的位置，位置从 1 开始编号。
提示：输出的应当是主链上的位置，而非碳原子的标号。
【样例 1 输入】
10 1 2 2 3 3 4 4 5 5 6 2 7 3 8 8 9 4 10【样例 1 输出】
6 6 7 2 2 4 1 3 0 0 0 0 0 0 0 0【样例 1 解释】
图 1: example-1 如上图所示，路径 (6, 7) 是符合条件的一条主链。当其作为主链时，{1}, {10} 分别 为位置 2, 4 上的甲基，{8, 9} 为位置 3 上的乙基。
同样合法的主链还包括：(1, 6)。而 (6, 9) 虽然长度也为 6，但是不是一条合法的主链。
【样例 2 输入】
8 1 2 2 3 3 4 4 5 2 6 3 7 7 8【样例 2 输出】
5 8 6 1 2 1 3 0 0 0 0 0 0【样例 2 解释】
如上图所示，以上烷烃主链有 (6, 8),(5, 6),(1, 8) 三种选法，都是合法的。
图中所示的为 (6, 8) 这条主链，按照这条主链可能得到 2-甲基-3-乙基戊烷或者 4-甲 基-3-乙基戊烷两种命名结果。根据最低系列原则，应当取“2-甲基-3-乙基戊烷”作为命 名结果，对应输出如样例所示。
【样例 3 输入】
13 1 2 2 3 3 4 4 5 3 6 6 7 7 8 6 9 2 10 3 11 11 12 4 13【样例 3 输出】
6 8 13 2 2 4 1 3 1 3 0 0 0 0 0 0 0 0 0 0【样例 4】 见 /ex_name4.in 与 /ex_name4.out。 样例 4
【测试点约束】
对于所有测试点，$1 ≤ n ≤ 5 × 10^5$。
本题采. 用. 捆. 绑. 评. 测. ，你在一个子任务中的得分是该子任务中所有测试点得分的最小 值。
每个子任务的具体限制见下表：
子任务编号 n ≤ 分数 1 300 17 2 3000 24 3 5 × 105 59
| 子任务编号 | n ≤ | 分数 |
|---|---|---|
| 1 | 300 | 17 |
| 2 | 3000 | 24 |
| 3 | $5 × 10^5$ | 59 |
【计分规则】 • 如果你的答案中，选取的主链不合法，且长度与合法的主链长度不同，则不能获得 任何分数。提示信息为 Wrong Answer[1].
• 如果你的答案中，选取的主链不合法，但是长度与合法的主链长度相同，可以获得 该测试点 12% 的分数。提示信息为 Wrong Answer[2].
• 如果你的答案中，选取的主链合法，但是对应的命名结果和该主链对应的命名结果 不符的，可以获得该测试点 35% 的分数。其中如果某烷基数量不正确。提示信息为 Wrong Answer[3]；
若是该烷基所在的位置不对，提示信息为 Wrong Answer[4].
• 如果你的答案完全正确，可以获得全部分数。提示信息为 Accepted。
【提示】
Q1：什么是链烃？
A1：链烃就是只由碳原子和氢原子组成，所有的碳之间都由碳-碳单键连接且不形成 环的有机化合物。当一个碳只和不足 4 个碳原子有共价键时，剩余共价键由碳-氢键补足， 我们无需过多考虑。在本题中，我们可以简单地认为碳原子连接形成一棵每个点度数不 超过 4 的无标号树。
Q2：什么是系统命名法？
A2：有机化合物种类繁多，数目庞大，即使同一分子式，也有不同的同分异构体。中 国 1980 年《有机化学命名原则》增订本规定了链烃的系统命名法的命名规则。
命名链烃时，首先要确定主链。确定主链的原则是：
1. 首先考虑链. 的. 长. 短，. 长. 的. 优. 先. 。
2. 若有两条或多条等长的最长链时，则根据支. 链. 的. 数. 目. 来确定主链，多. 的. 优. 先. 。为 方便描述，这里我们将支链的数量定义为“不在主链上，且与主链上的碳原子由共价键 直接连接的碳原子个数”。如果你了解支链的严谨定义，不难发现这两种描述是等价的。
3. 若仍无法分出哪条链为主链，则依次考虑下面的原则，侧链位次小的优先，各侧 链碳原子数多的优先，侧分支少的优先。
主链确定后，要根据最低系列原则 (lowest series principle) 对主链进行编号。最低系 列原则的内容是：使取代基的号码尽可能小，若有多个取代基，逐个比较，直至比出髙低 为止。最后，根据有机化合物名称的基本格式写出全名。
为降低题目难度，且因其在实际中应用较少，我们不考虑主链选取中第 3 条的内容。
我们认为如. 果. 一. 条. 链. 是. 这. 颗. 链. 烃. 中. 最. 长. 的. 一. 条. 碳. 链，. 并. 且. 在. 相. 同. 长. 度. 的. 碳. 链. 中，. 其. 支. 链. 数. 量. 是. 能. 达. 到. 的. 最. 多. 的，. 那. 么. 它. 就. 是. 一. 条. 合. 法. 的. 主. 链. 。一个链烃可能存在多条合法的主 链，任意输出一条即可，但接下来的命名必须与这条选好的主链相对应。
在本题中，最低系列原则我们如下定义：
1. 如果对于一条主链有多种可能导致命名结果不同的选取取代基的方法，那么我们 要求甲基多者优先；
2. 如果甲基数量相同，对于所有甲基的位置升序排列而成的序列，字典序小者优先；
3. 如果以上仍相同，则同理依次比较乙基、丙基……的情况，直到不同为止。