题目背景

作为年级第一大风流人物，Steve 总会给自己找很多东西，包括但不限于 npy。Steve 看上了 Ada，并试图接近她，然而 Ada 并不是那么乐意。

题目描述

提示：你可以阅读题目描述末尾的形式化题面。

Steve 所在的校园有 $n$ 间教室，编号为 $1$ 到 $n$，有 $n-1$ 条走廊将其连通。也就是说，教室和走廊构成了一棵树。每条走廊都有一定的长度 $w_i$，经过这条走廊的时间等于其长度的数值。

Steve 喜欢在校园里游荡。当然，他希望最后能走到自己的教室 $s$ 或 Ada 的教室 $t$。但由于学校过于错综复杂，且 Steve 不想走回头路，所以他想到了如下方案：

对于每个教室（Steve 和 Ada 的教室除外，这两个教室周围不应该有任何标牌），在一条与其相连的边立上标牌。每次走到这个教室，就从立了标牌的边出。

Steve 可能会在学校的任何一个教室出现，所以一方面，Steve 需要让他从每个教室都能跟着标牌回到他的或 Ada 的教室。另一方面，他希望从学校所有教室走到目的地的时间总和尽可能小。

由于 Steve 又要去找 Ada 了，所以请你帮他完成这个任务。

形式化题意

给定一棵 $n$ 个节点的无根树和两个关键点 $s,t$，要求对所有边定向，满足：

• 每条边要么是有向边，要么被删除；
• 每个点（除 $s,t$）出度恰好为 $1$，$s,t$ 出度为 $0$；
• 每个点都可以顺着有向边到达 $s$ 或 $t$。

求每个点到 $s$ 或 $t$ 的距离总和最小值。

输入格式

第一行输入三个正整数 $n$，$s$，$t$。

接下来 $n-1$ 行，每行输入三个正整数 $u_i$，$v_i$，$w_i$，代表一条树边 $(u_i,v_i)$，权值为 $w_i$。

输出格式

输出第一行一个正整数，代表最小的权值和。

接下来一行，输出一个字符串 $S$，要求：

• $S_i=\texttt{0}$，指第 $i$ 条边两边均不立标牌；
• $S_i=\texttt{1}$，指第 $i$ 条边在 $u_i$ 处立标牌；
• $S_i=\texttt{2}$，指第 $i$ 条边在 $v_i$ 处立标牌。

本题使用自定义校验器评测。如果有多种方案，输出任意一种。

5 1 5
1 2 1
2 3 1
3 4 1
4 5 1

4
2201

13 4 5
1 3 3
2 3 2
6 4 5
7 4 10
4 8 2
11 8 3
5 13 6
8 13 5
8 3 4
10 5 8
12 10 3
13 9 9

85
111121202112

见下发文件 corridor/corridor3.in

见下发文件 corridor/corridor3.ans

见下发文件 corridor/corridor4.in

见下发文件 corridor/corridor4.ans

提示

样例 1 解释

2011 也是合法的答案，但 2211，1102 等都不是。

样例 2 解释

下图是取到样例中最优解的状态（$(8,13)$ 这条边没有画出）:

样例 3 解释

该样例满足子任务 2 的限制条件。

样例 4 解释

该样例满足子任务 5 的限制条件。

---

下发文件中还有 checker.cpp 可判定答案是否合法。使用时，先编译（设二进制文件为 checker（Linux/MacOS）或 checker.exe（Windows）），然后在终端输入如下命令：

./checker in.txt out.txt ans.txt

如果你使用了 Windows 系统且无法运行上述命令，请尝试：

checker.exe in.txt out.txt ans.txt

其中 in.txt、out.txt、ans.txt 分别是放在同一目录下的输入文件、选手输出、标准答案。

结果可能有如下中的一种：

• ok：结果正确，可以得到满分；
• wrong answer：第一行答案错误；
• points 0.60：第一行答案正确，第二行答案错误。

对于所有非满分情况，会有附加消息，意义如下：

• A x y：第一行答案错误，标准答案是 $x$，选手答案是 $y$；
• B：第二行长度不符合条件；
• C：第二行出现非法字符；
• D：第二行给出的构造不满足题目中关于度数的限制；
• E x y：第二行给出的构造产生的答案是 $y$，而实际上答案是 $x$。

该校验器和最终评测时采用的校验器可能有所不同。

注意下发文件的输出样例中只有最优答案，没有构造方案。

数据规模与约定

本题捆绑测试。对于所有数据，$3\le n\le 3\times 10^5$，$1\le w_i\le2\times 10^8$，$1\le s,t\le n$，$s\neq t$。

$$\def\arraystretch{1.5} \begin{array}{c|c|c||c|c}\hline \bf 子任务 & \bf 分值 & \bf 依赖 & n\le & \bf特殊性质 \\ \hline \hline 1 & 10 & / & 10 & /\\\hline 2 & 15 & 1 & 18 & /\\\hline 3 & 15 & / & / & v_i=u_i+1\\\hline 4 & 10 & / & / & u_i=1\\\hline 5 & 20 & / & / & 存在边\ (s,t)\\\hline 6 & 30 & 2\sim5 &/ & / \end{array} $$

如果你计算出了正确的答案，但是你的构造是错误的，那你将得到该测试点 $60\%$ 的分数。注意即使你只实现了第一小问，请依旧在第二行输出任意一个非空字符串，否则可能会不计分。

本题中的依赖指：某子任务的得分占比不能超过其所依赖的子任务得分占比。比如，一选手子任务 $1$ 得到 $60\%$ 的分数，则他的子任务 $2$ 就不会超过对应的 $60\%$ 分数，即不超过 $9$ 分。

答案可能很大，请注意你使用的数据类型。

---

到毕业为止，Steve 也没有追到 Ada。What a sad story. :-(