James 是 Yuland 的市长，该国由 $n$ 个城市组成，城市之间由 $m$ 条不同长度的双向道路连接。保证从任何一个城市出发，仅通过这些道路即可到达其他任何城市。注意，同一对城市之间可能存在多条道路。
每个城市可以开设一家兔子商店或鸭子商店，但不能同时开设两种。每个城市的居民都希望收集这两种动物。一个城市的“不便程度”定义为该城市到最近的兔子商店的距离与到最近的鸭子商店的距离中的较大值。
James 尚未建造商店，他需要你的帮助来决定在哪些城市建造哪种商店，以使得所有城市的不便程度的最大值最小化。
输入格式
程序必须从标准输入读取数据。 第一行包含两个整数 $n, m$。 接下来的 $m$ 行，每行包含 3 个整数 $u[i], v[i], w[i]$，表示一条连接城市 $u[i]$ 和 $v[i]$、长度为 $w[i]$ 的道路。
输出格式
程序必须打印到标准输出。 第一行应为所有城市不便程度的最大值的最小值。 下一行应为一个长度为 $n$ 的字符串，由字符 B 或 D 组成，其中第 $i$ 个字符表示你在第 $i$ 个城市选择建造兔子商店（B）还是鸭子商店（D）。如果存在多种建造方案使得最大不便程度达到第一行所述的最小值，则输出任意一种均可。
数据范围
对于所有测试用例，输入满足以下限制：
- $2 \le n, m \le 500\,000$
- $1 \le u[i], v[i] \le n$
- $1 \le w[i] \le 10^9$
- 保证从任何一个城市出发，仅通过这些道路即可到达其他任何城市。
你的程序将在满足以下限制的输入实例上进行测试：
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 0 | 0 | 样例测试用例 |
| 1 | 7 | $n \le 16$ |
| 2 | 13 | $m = n - 1, u[i] = i, v[i] = i + 1$ |
| 3 | 18 | $m = n - 1$ |
| 4 | 24 | $w[i] = 1$ |
| 5 | 38 | 无附加限制 |
样例
输入格式 1
3 3 1 2 3 2 3 1 1 3 2
输出格式 1
2 BBD
说明
[2, 1, 1]
输入格式 2
5 6 3 2 3 4 2 1 5 3 9 1 3 5 1 4 2 2 3 1
输出格式 2
9 DBDDB
说明
[3, 1, 1, 1, 9]