Graph (Directed Graph) Traversal Write the code to perform the BFS and DFS traversal for the Directed Graph.

Operations:
AV – Add the vertex  [Note: Code is provided in the template]
AE – Add edge [Note: Code is provided in the template]
DFS-  DFS traversal 
traverse the graph using dfs from start node. The function must print the nodes and edges in the order in which they are visited, and mention if it is a tree edge(edge which is considered part of dfs/bfs traversal) or forward or backward edge or cross edge
BFS – BFS traversal 
 traverse the graph using bfs from start node.  The function must print the nodes and edges in the order in which they are visited, and mention if it is a forward or cross edge

Input:

• The first line contains number of operations.
• Each line of the subsequent lines contains operation followed inputs related to the operations as described in below

    
  AV  vertexnumber  
  AE  SrcVertextNo DstVertextNo weight
  DFS startVertextnumber         
  BFS startVertextnumber
  

DFS /BFS types of edges

1. Tree edge (t) - an edge to a new vertex which is not yet visited.
2. Back edge (b)- an edge to an ancestor.
3. Forward edge(f) - an edge to visited Vertex from ancestor to descendant
4. Cross edge (c)- an edge to a visited vertex which is not a descendant

Sample Input :

AV 1
AV 2
AV 3
AV 4
AE 1 2 2
AE 2 3 1
AE 2 1 4
AE 1 3 6
AE 1 4 2
AE 4 3 1
DFS
BFS

Sample Output:

1(t)2 2(t)3 2(b)1 1(f)3 1(t)4 4(c)3
1(t)2 1(t)3 1(t)4 2(b)1 2(c)3 4(c)3

Explanation for DFS and BFS Output:

For the sample input graph  
1--->2 --->3
2--->1
1--->3
1--->4
4--->3

DFS traversal 
1--->(t)2--->(t)3
2--->(b)1
1--->(f)3
1--->(t)4
4--->(c)3
Hence output of the DFS should be printed as follows
1(t)2 2(t)3 2(b)1 1(f)3 1(t)4 4(c)3

BFS traversal 
1--->(t)2 1--->(t)3  1--->(t)4 
2--->(b)1 2--->(c)3  
4--->(c)3

Hence output of the BFS should be printed as follows
1(t)2 1(t)3 1(t)4 2(b)1 2(c)3 4(c)3