Kanton, znany również jako Kanton i „Cité des Rams”, to dynamiczna metropolia z ponad 2200-letnią historią. Jako kluczowy punkt startowy starożytnego Morskiego Szlaku Jedwabnego, był ważnym portem handlu międzynarodowego od czasów dynastii Qin i Han. W zeszłym roku 15. Krajowe Igrzyska zakończyły się sukcesem w Kantonie. Duch ciężkiej pracy sportowców wciąż kwitnie w tym mieście.

Obraz 1 : „Dawanji” na Międzynarodowym Lotnisku Guangzhou Baiyun

Teraz ty i twój partner planujecie podróż po Kantonie. Jest $n$ atrakcji, które chcecie odwiedzić. Ponadto planujecie pozostać w Kantonie przez $m$ dni. Istnieje $n-1$ relacji między atrakcjami. Każda relacja łączy dwie atrakcje, wskazując, że są one ściśle powiązane historią lub krajobrazem. Co więcej, dowolne dwie różne atrakcje mogą być osiągnięte przez jedną lub więcej relacji, co oznacza, że relacje tworzą drzewo. Decydujecie odwiedzić każdą atrakcję dokładnie raz. Niech $b_i$ będzie dniem, w którym odwiedzana jest atrakcja $i$. Wasz plan musi spełniać:

• Hotel, który zarezerwowałeś na $i$-ty dzień, znajduje się w pobliżu atrakcji $a_i$. Oznacza to, że musisz odwiedzić atrakcję $a_i$ dnia $i$. Innymi słowy, $b_{a_i} = i$ dla każdego $i = 1, 2, \dots, m$.
• Dla każdej atrakcji $i$ ($1 \le i \le n$) liczba relacji łączących ją z innymi atrakcjami odwiedzonymi tego samego dnia (dnia $b_i$) jest nie mniejsza niż liczba takich relacji dla dowolnego innego dnia. Innymi słowy, dla każdego $u = 1, 2, \dots, n$ i każdego $t = 1, 2, \dots, m$ musi zachodzić $\sum_{(u,v) \in E} [b_v = b_u] \ge \sum_{(u,v) \in E} [b_v = t]$, gdzie $E$ jest zbiorem wszystkich relacji.

Zatem zaplanuj teraz swoją podróż! Zbuduj dowolne $b_1, b_2, \dots, b_n$ spełniające powyższe warunki lub udowodnij, że jest to niemożliwe.

Wejście

Każdy przypadek testowy zawiera wiele przypadków testowych. Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \le t \le 10^5$), oznaczającą liczbę przypadków testowych. Opis przypadków testowych jest kontynuowany. Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n, m$ ($1 \le m \le n \le 10^5$, $1 < \sum n, \sum m \le 10^6$), oznaczające liczbę atrakcji i liczbę dni pobytu. Drugi wiersz zawiera $m$ liczb całkowitych $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$, $a_i \ne a_j$ dla $i < j$), oznaczających, że musisz odwiedzić atrakcję $a_i$ w dniu $i$. Kolejnych $n-1$ wierszy, każdy zawiera dwie liczby całkowite $u_i, v_i$ ($1 \le u_i, v_i \le n$), oznaczające relację.

Wyjście

Dla każdego przypadku testowego, jeśli nie możesz stworzyć poprawnego planu, wypisz NO. W przeciwnym razie wypisz dwa wiersze. Pierwszy wiersz zawiera słowo YES, a drugi wiersz zawiera $b_1, b_2, \dots, b_n$ ($1 \le b_i \le m$) wskazujące na twój plan. Jeśli istnieje wiele poprawnych odpowiedzi, możesz wypisać dowolną z nich.

Przykład

Wejście 1

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

Wyjście 1

YES
1
YES
1 1 2 2
NO
YES
1 2 2 3 3 1

Uwagi

Obraz 2 : Rysunek przykładowy dla przypadku testowego 4