Border-Crossing Salesman

Time limit2sMemory limit128 MB

Summary

Given a convex polyhedron whose faces are countries, build the face-adjacency graph from shared edges and answer BFS shortest-path queries between faces.

Level: Medium6 of 10
Topics: Geometry, Graph, BFS, Implementation
Solved: No attempts yet

Problem

Long before international trade treaties, a salesman had to pay taxes at every border he crossed. Given two countries, find the minimum number of borders that must be crossed to travel from one to the other.

The surface of Earth is modeled as a closed convex three-dimensional polyhedron. Each polygonal face represents one country. You may not cross a border at a point where three or more countries meet.

Input

The first line contains the number of countries c (4 <= c <= 6000). The next c lines each have the form n x1 y1 z1 ... xn yn zn, describing the n vertices of one closed polygon in order (3 <= n <= 20).

The next line contains the number of queries m (0 < m <= 50). Each of the following m lines contains two country numbers ca cb. Countries are numbered starting from 1.

No vertex lies on the segment between two connected vertices. Every coordinate x, y, and z satisfies -10^6 <= x, y, z <= 10^6. Within one country, no two non-adjacent edges share a point.

Output

For each query, output the minimum number of borders that must be crossed to travel from ca to cb.

Examples1

Example 1

Input

6
4 0 0 0 0 0 1 0 1 1 0 1 0
4 1 0 0 1 0 1 1 1 1 1 1 0
4 0 0 0 1 0 0 1 0 1 0 0 1
4 0 1 0 1 1 0 1 1 1 0 1 1
4 0 0 0 0 1 0 1 1 0 1 0 0
4 0 0 1 0 1 1 1 1 1 1 0 1
2
1 2
1 3

Expected output

2
1