约翰是一个农场主,他的农场有n块田,编号从 到 ,这 块田通过 条双向道路相连(数据保证这n块田都是联通的),我们假设第块田会产生 kg 的收益,现在约翰想把农田的工作全部交给自己的两个孩子,划分方式必须满足以下规则:
1.每一块田都需要恰好被分给一个孩子.
2.分给两个孩子的农田必须是联通的.就是说对于任意一个孩子在划分给自己的任意一块田,都可以不经过另外一个孩子的田,到达自己的任意一块田.
3.划分给两个孩子的收益必须尽可能的相等,如果无法相等,年长的孩子会得到大的那一份.
对于第 块田,如果你要把它分给年长的孩子,请输出A
,否则输出B
.
第一行输入两个整数分别代表 接下来 行,每个两个整数,代表这两块农田通过一条双向道路直接相连,数据保证没有重边和自环
输出一个字符串,代表答案
3 2
1 3
3 2
ABA
6 6
3 5
2 6
1 3
3 6
5 1
4 6
BABABA