Consider expressing the placement of the eight pieces with a nine-character string \(s_1 s_2 \ldots s_9\). \(s_i\) is defined to be \(j\) when Vertex \(i\) has Piece \(j\) on it, or \(9\) if Vertex \(i\) is an empty vertex.
For example, the pieces on the complete puzzle is represented by a string 123456789. Also, through the steps shown in the description of Sample Input \(1\), the placements of pieces are: 931456782 \(\rightarrow\) 231456789 \(\rightarrow\) 291456783 \(\rightarrow\) 921456783 \(\rightarrow\) 129456783 \(\rightarrow\) 123456789.

Since a placement of pieces is expressed as a permutation of characters from 1 through 9, there are \(9!\) possible placements of pieces.
Also, from a state \(s_1 s_2 \ldots s_9\), if and only if “\(s_i = \) 9 or \(s_j = \)9” and “there exists an edge connecting Vertex \(i\) and Vertex \(j\)”, then we can transit to the state \(s_1 \ldots s_{i-1} s_j s_{i+1} \ldots s_{j-1} s_i s_{j+1} \ldots s_9\) where \(s_i\) and \(s_j\) are swapped, in a single operation.

Considering an undirected graph where the vertices are \(9!\) possible states and every pair of states that can be transited to each other are connected with an edge, the answer for this problem is “the shortest distance from the initial state to the state 123456789” on this undirected graph.
This can be computed by doing Breadth-First Search (BFS) on this graph. In order to store “the shortest distance from the initial state to each state \(s_1 s_2 \ldots s_9\),” we may use an associated array that maps each string \(s_1 s_2 \ldots s_9\) to the shortest distance.

A sample code in C++ language follows.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;

int main(void)
{
  int m;
  cin >> m;

  vector<int> G[10];
  int u, v;
  for(int i = 1; i <= m; i++){
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }

  int p; string s = "999999999";
  for(int i = 1; i <= 8; i++){
    cin >> p;
    s[p-1] = i + '0';
  }

  queue<string> Q;
  Q.push(s);
  map<string, int> mp;
  mp[s] = 0;

  while(Q.size()){
    string s = Q.front(); Q.pop();
    for(int i = 1; i <= 9; i++) if(s[i-1] == '9') v = i;

    for(auto u : G[v]){
      string t = s;
      swap(t[u-1], t[v-1]);
      if(mp.count(t)) continue;
      mp[t] = mp[s] + 1;
      Q.push(t);
    }
  }
  if(mp.count("123456789") == 0) cout << -1 << endl;
  else cout << mp["123456789"] << endl;

  return 0;
}