Given an undirected graph and its spanning tree T and starting node $0,$ return true if the spanning tree T is a valid traversal tree by some DFS on G from starting node $0,$ otherwise return false.

$$

Input:

Line $0[$number of nodes V$][$number of edges E$]$

The following V lines: each line contains a space separated numbers indicating adjacency list of node $0,1,2,...$

$1$ line: the starting node label

V$-1$ lines: the V$-1$ tree edges.

$$

Output:

true if the spanning tree is valid DFS traversal tree

false otherwise

Example $1$

Input:

$33$

$12$

$02$

$01$

$0$

$01$

$02$

Output: false

Explanation: For this small problem there is only two valid DFS traversal tree starting from node $01.0-1,1-22.0-2,2-1$ The given tree $0-1,0-2$ is not one of the the two.

Example $2$

Input:

$33$

$12$

$02$

$01$

$0$

$02$

$12$

Output: true

Example $3$

Input:

$33$

$12$

$02$

$01$

$0$

$01$

$12$

Output: true

Starter code in the image

#include

#include

#include

#include

#include

using namespace std;

int main$()$

$\{$

int n$,$ m;

cin $>>$ n $>>$ m;

cout $$ "nodes $"$ n edges $"$ m $$ endl;

vector$>$ adj$($n$)$;

string line;

getline$($cin$,$line$)$; $//$ consume the linefeed of the first line

for $($int i$=0$; i$>$ num$)\{$

adj$[$i$].$insert$($num$)$;

$\}$

$\}$

int start;

cin $>>$ start;

cout $$ "start $"$ start $$ endl;

vector$>$ T$($n$)$;

for $($int i$=0$; i$>$ u $>>$ v;

T$[$u$].$insert$($v$)$;

T$[$v$].$insert$($u$)$;

$\}$

$//$ now the adj$[$i$]$ is the adjacency list for node i in graph G

$//$ and T$[$i$]$ is the adjacency list for i in tree T

$\}$