Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3749
Chameleon

Time Limit: 6 Seconds      Memory Limit: 65536 KB

Given n groups of integers(all the integers are distinct). You should answer Q queries in this problem.

Each query contains a pair of integers (i, j). For each query, you must perform below operations:

1. List the i-th group and the j-th group in a line. These integers form an array ci.
2. Sort ci in ascending order.
3. Answer this question: how many i satisfy that GroupIDi-1 GroupIDi after sorting. Here GroupIDi equals to the group id which ci belongs to. That means the value of GroupID must be either i or j in this query.

#### Input

The input file contains multiple test cases.

Each case begin with an integer n which indicate the amount of group. The following n lines each describe a group of integers. The format of these lines is:

mi ai1 ai2 ai3 ... aimi (1 ≤ in, 1 ≤ aij ≤ 109)

We guarantee that m1 + m2 + m3 + ... + mn ≤ 105

There is a number Q(1 ≤ Q ≤ 105) after these groups of integers. This number is followed by Q lines, each contains two numbers (i, j)(1 ≤ i, jn and ij) which describe a query.

Process to the End Of File.

#### Output

Output an integer in a line for each query.

```2
3 1 5 8
3 2 6 7
1
1 2
```

```4
```

#### Hint

In the sample, we get c = {1, 5, 8, 2, 6, 7}, GruopID = {1, 1, 1, 2, 2, 2}.

After sorting, it becomes c = {1, 2, 5, 6, 7, 8}, GruopID = {1, 2, 1, 2, 2, 1}.

Author: CHEN, Weijie
Source: ZOJ Monthly, January 2014
Submit    Status