Überprüfung der Gültigkeit einer BFS-Traversierung

Angenommen, wir haben einen Baum (ein Graph ohne Zyklen) mit n Knoten und eine BFS-Traversierung, die die Reihenfolge der vom Algorithmus besuchten Knoten angibt. Unsere Aufgabe ist zu prüfen, ob diese Besuchsreihenfolge überhaupt möglich ist.

Der Algorithmus startet immer beim Knoten 1 und durchläuft die benachbarten Knoten in beliebiger Reihenfolge. Ihr Programm soll Yes ausgeben, wenn die angegebene Traversierung für den gegebenen Baum möglich ist, und andernfalls No.

Zur Erinnerung: Ein Baum hat immer n-1 Kanten.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl n (1 ≤ n ≤ 100 000).

Die folgenden n-1 Zeilen enthalten jeweils zwei ganze Zahlen (1 ≤ ≤ n), die die Kanten des Baums darstellen.

In der darauffolgenden Zeile stehen n durch Leerzeichen getrennte ganze Zahlen (1 ≤ ≤ n), die die Besuchsreihenfolge des BFS-Algorithmus angeben.

Ausgabe

Das Programm soll Yes ausgeben, wenn das beschriebene Szenario gültig ist, andernfalls No.

Beispiele