Hide

Problem I
Mårtens DFS

Languages en sv

Du får givet en enkel, sammanhängande graf $G$ med $N$ hörn. Varje hörn i $G$ har numrerats med tal mellan $0$ och $N-1$.

Avgör om en lista med heltal $L$ är en giltig djupet först-sökning. En giltig djupet först-sökning är en som kan genereras av följande procedur, anropad med något argument mellan $0$ och $N - 1$:

DFS(start):
  skriv ut start
  sett[start] = true
  för varje v : grannar(start):
    om inte sett[start]:
      DFS(v)

Observera att grannarna till ett visst hörn kan gås igenom i vilken ordning som helst av Mårtens algoritm.

Indata

Den första raden innehåller två heltal $1 \le N \le 100\, 000$ och $0 \le E \le 300\, 000$, antalet hörn och kanter i $G$.

De nästa $E$ raderna innehåller två heltal $0 \le a, b \le N - 1$, som beskriver en kant i $G$ mellan hörnen $a$ och $b$.

Den sista raden kommer innehålla en (möjligtvis tom) blankstegs-separerad lista $L$ med heltal.

Utdata

Du ska skriva ut YES om $L$ är en giltig djupet först-sökning. Annars ska du skriva ut NO.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

1

19

$1 \le N \le 8$, $1 \le E \le 28$

2

43

$1 \le N \le 1\, 000$, $1 \le E \le 5\, 000$

3

38

Inga ytterligare gränser

Sample Input 1 Sample Output 1
4 3
0 1
1 2
2 3
0 1 2 3
YES
Sample Input 2 Sample Output 2
4 3
0 1
1 2
2 3
2 1 0 3
YES
Sample Input 3 Sample Output 3
4 3
0 1
1 2
2 3
2 1 3 0
NO
Sample Input 4 Sample Output 4
4 3
0 1
1 2
2 3
0 1 2
NO
Sample Input 5 Sample Output 5
4 3
0 1
1 2
2 3
1 0 4 3 2
NO