给定一棵含有
现在,我们想要给树的每条边一个定向。任何一个定向都可以用一个长度为
给定
一个完美定向定义为:在此定向下,对于任意
试求在所有完美定向中,所对应的字符串字典序最小的定向。数据保证存在至少一个完美定向。
定义字符串
输入格式
输入的第一行包含三个非负整数
接下来
接下来
输出格式
输出一行包含一个字符串
样例一
input
0 4 2
1 2
2 3
3 4
3 2
1 4
output
001
explanation
在该样例中,若
样例二
input
0 6 8
5 1
2 3
1 2
5 6
4 3
4 3
5 1
6 3
5 4
1 4
5 2
3 6
6 2
output
10101
explanation
在该样例中,一组完美定向必定满足
样例三
见附件下载中的 ex_tree3.in
与 ex_tree3.ans
。
这个样例满足测试点
样例四
见附件下载中的 ex_tree4.in
与 ex_tree4.ans
。
这个样例满足测试点
样例五
见附件下载中的 ex_tree5.in
与 ex_tree5.ans
。
这个样例满足测试点
样例六
见附件下载中的 ex_tree6.in
与 ex_tree6.ans
。
这个样例满足测试点
数据范围
对于所有测试数据保证
数据保证存在至少一个完美定向。
测试点编号 | 特殊性质 | ||
---|---|---|---|
无 | |||
A | |||
B | |||
无 | |||
B | |||
无 | |||
- 特殊性质 A:保证
出现在 中当且仅当 且 在树上不相邻。 - 特殊性质 B:保证树上编号为
的顶点与其他每个顶点均相邻。
时间限制:
空间限制: