#arc063c. [arc063_c]Integers on a Tree

[arc063_c]Integers on a Tree

問題文

NN 頂点の木があり、頂点には 1,2,...,N1, 2, ..., N と番号が振られています。ii (1iN11 ≦ i ≦ N - 1) 番目の辺は頂点 AiA_i と頂点 BiB_i を結んでいます。

高橋君は木の KK 個の頂点に整数を書き込みました。具体的には、各 1jK1 ≦ j ≦ K について、頂点 VjV_j に整数 PjP_j を書き込みました。その後、高橋君は居眠りを始めました。

木を見つけた青木君は、残りのすべての頂点に整数を書き込み、高橋君を驚かせようとしています。高橋君を驚かせるためには、木が次の条件を満たさなければなりません。

  • 条件: 辺で直接結ばれた 22 つの頂点に書かれている整数の差がちょうど 11 である。

残りのすべての頂点に書き込む整数を工夫することで、木が条件を満たすようにできるか判定してください。もし可能な場合は、どのように整数を書き込めばよいかを具体的にひとつ求めて下さい。

制約

  • 1N1051 ≦ N ≦ 10^5
  • 1KN1 ≦ K ≦ N
  • 1Ai,BiN1 ≦ A_i, B_i ≦ N (1iN11 ≦ i ≦ N - 1)
  • 1VjN1 ≦ V_j ≦ N (1jK1 ≦ j ≦ K) (21:18, 制約の誤記を修正)
  • 0Pj1060 ≦ P_j ≦ 10^6 (1jK1 ≦ j ≦ K)
  • 与えられるグラフは木になることが保証される
  • VjV_j はすべて相異なる

入力

入力は以下の形式で標準入力から与えられる。

NN A1A_1 B1B_1 A2A_2 B2B_2 :: AN1A_{N-1} BN1B_{N-1} KK V1V_1 P1P_1 V2V_2 P2P_2 :: VKV_K PKP_K

出力

残りのすべての頂点に書き込む整数を工夫することで木が条件を満たすようにできるならば Yes を、できないならば No を出力せよ。

条件を満たせる場合、追加で NN 行出力せよ。このうちの vv (1vN1 ≦ v ≦ N) 行目には、頂点 vv に書かれる整数を出力せよ。条件を満たすような整数の書き込み方が複数ある場合、そのうちいずれかひとつを出力すればよい。


入力例 1

5
1 2
3 1
4 3
3 5
2
2 6
5 7

出力例 1

Yes
5
6
6
5
7

はじめ、木は以下の図のような状態である。頂点のそばに書かれた数が頂点番号を、頂点の中に書かれた青い数が元から書き込まれていた整数を表す。

6da26f89839711a520acdf5c3e1cc309.png

青木君はたとえば次のように残りの頂点に整数を書き込むことで木が条件を満たすようにできる。これは出力例 11 に対応している。

1858d5af5a2c0e51aca39a39d765debb.png

木が条件を満たしていれば、これとは異なった出力でも AC となることに注意せよ。たとえば、入力例 11 に対しては

Yes
7
6
8
7
7

という出力でも正答となる。


入力例 2

5
1 2
3 1
4 3
3 5
3
2 6
4 3
5 7

出力例 2

No

入力例 3

4
1 2
2 3
3 4
1
1 0

出力例 3

Yes
0
-1
-2
-3

新たに書き込む整数は負になったり 10610^6 を超えたりしても構わない。