无根树转有根树

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file wgs.in Output file 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。 

【提示】

在此键入。

【来源】

在此键入。