无根树转有根树

成绩 开启时间 2014年09月19日 星期五 10:08
折扣 0.8 折扣时间 2014年09月26日 星期五 10:08
允许迟交 是 关闭时间 2014年09月26日 星期五 10:08
输入文件 wgs.in 输出文件 wgs.out

【题目描述】

输入一个n个结点的无根树的各条边，并指定一个根结点，要求把该树转化为有根树，输出各个结点的父亲编号。n≤10^6，如图所示。

【输入格式】

第1行：两个空格隔开的整数n，u；n是树的节点数，u是根节点编号。

第2～n行：每行包含二个整数X,Y，表示节点X，节点Y之间有边。（节点编号从0开始）

第n+1行，一个整数m

第n+2行，m个用空格隔开的整数，表示需要输出父亲的结点编号。

【输出格式】

一行，m个用一个空格隔开的整数，为m个节点的父亲编号。

【样例输入】 

8 1
0 1 
0 2 
0 3 
1 4 
1 5 
5 6 
5 7
8
0 1 2 3 4 5 6 7

【样例输出】 

1 -1 0 0 1 1 5 5
输出解释：
1号节点没有父亲，输出-1。

【提示】

在此键入。

【来源】

在此键入。