問題文
N 頂点 N−1 辺からなる根付き木 T と、頂点の部分集合 V に対して、木の圧縮を以下のように定義します。
- 圧縮後の木の頂点の集合を V′、辺の集合を E′ とする。
- V′:={lca(x,y)∣x,y∈V}
- E′:={{x,y}∣x,y∈V′,x=y,Tのパス(x,y)にx,y以外のV′に含まれる頂点が現れない}
頂点 0を根とする根付き木 T と頂点の部分集合 V が与えられるので、これを圧縮してください。
制約
- 1≤N≤105
- 1≤∣V∣≤N
- 0≤xi,yi,ai<N
入力
入力はすべて整数である。
N
x_1 y_1
x_2 y_2
.
.
.
x_N-1 y_N-1
|V|
a_1 a_2 a_3 ... a_|V|
出力
|V'|
a_1 a_2 a_3 ... a_|V'|
x_1 y_1
x_2 y_2
.
.
.
x_|V'|-1 y_|V'|-1
1行目に V′ の要素数、2行目にV′ の要素を頂点番号順にソートしたものを、3行目以降に E′ の要素をソートしたものを出力してください。
辺のソートについて、{xi,yi}と{xi+1,yi+1}が(xi<yi)∧(xi+1<yi+1)∧(xi<xi+1∨(xi=xi+1∧yi<yi+1))
を満たすようにソートしてください。
サンプル
入力1
10
1 5
1 0
0 3
1 7
7 2
5 6
2 4
7 9
9 8
4
0 2 4 5
出力1
5
0 1 2 4 5
0 1
1 2
1 5
2 4
入力2
10
4 5
4 6
6 0
0 1
6 9
5 3
4 8
1 2
5 7
4
2 5 7 9
出力2
6
0 2 5 6 7 9
0 2
0 6
5 6
5 7
6 9