# A Peterson Graph Problem

The following graph G is called a Petersen graph and its vertices have been numbered from 0 to 9. Some letters have also been assigned to vertices of G, as can be seen from the following picture:
Let’s consider a walk W in graph G, which consists of L vertices W1, W2, …, WL. A string S of L letters 'A' – 'E' is realized by walk W if the sequence of letters written along W is equal to S. Vertices can be visited multiple times while walking along W.

For example, S = 'ABBECCD' is realized by W = (0, 1, 6, 9, 7, 2, 3). Determine whether there is a walk W which realizes a given string S in graph G, and if so then find the lexicographically least such walk. The only line of input contains one string S. If there is no walk W which realizes S, then output -1 otherwise, you should output the least lexicographical walk W which realizes S.

Examples:

```Input : s = 'ABB'
Output: 016
Explanation: As we can see in the graph
the path from ABB is 016.
Input : s = 'AABE'
Output :-1
Explanation: As there is no path that
exists, hence output is -1.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We apply breadth first search to visit each vertex of the graph.

 `// C++ program to find the ` `// path in Peterson graph ` `#include ` `using` `namespace` `std; ` ` `  `// path to be checked  ` `char` `S[100005];  ` ` `  `// adjacency matrix.  ` `bool` `adj[10][10]; ` ` `  `// resulted path - way  ` `char` `result[100005]; ` ` `  `// we are applying breadth first search ` `// here ` `bool` `findthepath(``char``* S, ``int` `v) ` `{ ` `    ``result[0] = v + ``'0'``; ` `    ``for` `(``int` `i = 1; S[i]; i++) { ` `         `  `        ``// first traverse the outer graph ` `        ``if` `(adj[v][S[i] - ``'A'``] || adj[S[i] - ` `                              ``'A'``][v]) { ` `            ``v = S[i] - ``'A'``; ` `        ``} ` ` `  `        ``// then traverse the inner graph ` `        ``else` `if` `(adj[v][S[i] - ``'A'` `+ 5] ||  ` `                 ``adj[S[i] - ``'A'` `+ 5][v]) { ` `            ``v = S[i] - ``'A'` `+ 5; ` `        ``} ` ` `  `        ``// if the condition failed to satisfy ` `        ``// return false ` `        ``else`  `            ``return` `false``; ` ` `  `        ``result[i] = v + ``'0'``; ` `    ``} ` ` `  `    ``return` `true``; ` `} ` ` `  `// driver code ` `int` `main() ` `{ ` `    ``// here we have used adjacency matrix to make ` `    ``// connections between the connected nodes ` `    ``adj[0][1] = adj[1][2] = adj[2][3] = adj[3][4] =  ` `    ``adj[4][0] = adj[0][5] = adj[1][6] = adj[2][7] = ` `    ``adj[3][8] = adj[4][9] = adj[5][7] = adj[7][9] = ` `    ``adj[9][6] = adj[6][8] = adj[8][5] = ``true``; ` `     `  `    ``// path to be checked ` `    ``char` `S[] = ``"ABB"``; ` `     `  `    ``if` `(findthepath(S, S[0] - ``'A'``) ||  ` `        ``findthepath(S, S[0] - ``'A'` `+ 5)) { ` `        ``cout << result; ` `    ``} ``else` `{ ` `        ``cout << ``"-1"``; ` `    ``} ` `    ``return` `0; ` `} `

Output:

```016
```

Graph Graph