Problem F
Fortunate Fees

Picture by Kjetil Ree, CC BY-SA 2.5

Fred is an autonomous AI working for Predetermined Corp, a company that specialises in delivering goods between predetermined cities in Europe. Fred, for instance, is always driving from city $u_0$ to city $v_0$ and straight back. In fact, every autonomous AI $i$ at Predetermined Corp drives from city $u_ i$ to $v_ i$ and back, and does nothing else.

This is pretty boring, because Predetermined Corp wants them to take the cheapest route possible every single time. As Predetermined Corp has struck an amazing deal with the EU, their entire fleet’s energy and upkeep costs are completely subsidised, and the only real cost comes from the road tolls they have to pay.

Of course, it’s not always obvious which route is the cheapest between two different cities. Fortunately for the AIs, IDI, the Intereuropean Department for Imposts, has a website with all the road tolls in Europe, making it trivial to compute the optimal route.

IDI is also responsible for deciding what the road tolls should be, and is about to change them once again. The process to do that is quite simple: For every road, they pick a random positive real number and let that be its road toll. This is quite the thrill for all the AIs at Predetermined Corp: They will still drive from $u_ i$ to $v_ i$ and back, but likely with a different route! Well, with the exception for the AIs that drive goods inside the same city ($u_ i = v_ i$), that is.

Fred knows that Predetermined Corp will never change an AI’s schedule, but he and the other AIs still dream of exploring the world. With IDI’s rather frequent changes to road tolls, they all wonder how many cities they will be able to visit given an infinite amount of time and an infinite amount of road toll changes.

Input

The first line contains two integers, $C$ and $T$: The number of cities and the number of AIs at Predetermined Corp.

Next follows $C$ lines. Each line starts with an integer $N_ i$, followed by $N_ i$ intervals $I_{i,j} = [s_{i,j},e_{i,j}]$. There is a two-way road between city $i$ and $k \in I_{i,j}$.

Finally, $T$ lines follow. Each line contains two integers $u_ i$ and $v_ i$, the cities AI $i$ drives between.

Output

Output $T$ lines, one for each AI. For each line $i$, print out the number of cities AI $i$ will eventually visit given an infinite amount of time.

Limits

• The cities and roads form a connected graph.

• $1 < C \leq 10\, 000$

• $0 \leq s_{i,j} \leq e_{i,j} < i$ and $e_{i,j} + 1 < s_{i,j+1}$

• $0 \leq T \leq 2\, 500$

• $0 \leq u_ i, v_ i < C$

• $\sum N_ i < 20\, 000$

7 2
0
0
1 [0,0]
2 [0,0] [2,2]
1 [3,3]
2 [1,1] [4,4]
2 [1,1] [5,5]
3 6
2 4

5
4

4 2
0
1 [0,0]
1 [0,1]
1 [0,0]
0 3
1 3

2
4

6 3
0
1 [0,0]
1 [1,1]
1 [0,1]
2 [0,1] [3,3]
2 [2,2] [4,4]
0 5
1 5
3 4

6
6
6