#include #include #include #include #include #include using namespace std; const int infinity = 1 << 30; struct Point { int x, y; Point() {} Point(int xx, int yy) : x(xx), y(yy) {} bool operator <(const Point& b) const { if(x != b.x) return x < b.x; return y < b.y; } bool operator ==(const Point& b) const { return x == b.x && y == b.y; } }; bool isAdj(const Point& a, const Point& b) { int dx = a.x - b.x; int dy = a.y - b.y; return dx != dy && abs(dx) <= 1 && abs(dy) <= 1; } pair interAdj(const Point& a, const Point& b) { bool f = true; Point first; for(int dx = -1; dx <= 1; ++dx) for(int dy = -1; dy <= 1; ++dy) if(dx != dy && isAdj(Point(a.x+dx, a.y+dy), b)) { if(f) { f = false; first = Point(a.x+dx, a.y+dy); } else return make_pair(first, Point(a.x+dx, a.y+dy)); } return make_pair(Point(infinity, infinity), Point()); } int n; struct Snake { vector v; bool valid(); void next(list& l) { Snake s = *this; nextR(l, s, 0); } void nextR(list& l, Snake& s, int d); bool operator <(const Snake& b) const { return v < b.v; } void print() const { for(int i = 0; i < n; ++i) cout << "(" << v[i].x << "," << v[i].y << ")"; cout << endl; } }; set stone; set cache; bool Snake::valid() { for(int i = 0; i < n; ++i) { for(int j = i + 2; j < n; ++j) { if(isAdj(v[i], v[j]) || v[i] == v[j]) return false; } if(stone.find(v[i]) != stone.end()) return false; } return true; } void Snake::nextR(list& l, Snake& s, int d) { if(d >= n) { if(s.valid() && cache.insert(s).second) l.push_back(s); return; } nextR(l, s, d+1); Point backup = v[d]; pair p; bool two = true; if(d == 0) { p = interAdj(v[d], v[d+1]); } else if(d == n-1) { p = interAdj(v[d-1], v[d]); } else { p = interAdj(v[d-1], v[d+1]); if(p.first.x == infinity) return; if(p.first == v[d]) swap(p.first, p.second); two = false; } s.v[d] = p.first; nextR(l, s, d+2); if(two) { s.v[d] = p.second; nextR(l, s, d+2); } s.v[d] = backup; } int Solve(Snake& start, int X, int Y) { list next, cur; cur.push_back(start); cache.insert(start); for(int step = 0; step <= 20; ++step) { for(list::iterator p = cur.begin(); p != cur.end(); ++p) { //if(step == 1) p->print(); if(p->v[0] == Point(X, Y)) return step; p->next(next); } cur.clear(); swap(cur, next); } return -1; } int main() { while(cin >> n && n) { stone.clear(); cache.clear(); Snake s; s.v.resize(n); for(int i = 0; i < n; ++i) { cin >> s.v[i].x >> s.v[i].y; } int m; cin >> m; for(int i = 0; i < m; ++i) { Point p; cin >> p.x >> p.y; stone.insert(p); } int x, y; cin >> x >> y; cout << Solve(s, x, y) << endl; } }