8690: Colourful Journey

Recently an epoch-making smart electric car developed by NIO company goes on sale. To celebrate, the chief test driver plans to drive the new car in Byteland for $q$ days.

Byteland has $n$ cities numbered from $1$ to $n$, and $n$ bi-directional roads connecting them. For each pair of cities, the driver can always arrive one from another one through these roads. There is a garage selling car paints of some colours on each road. Every time when the driver passes through a road, he will choose one colour of car paints from the garage and repaint the car if that colour is different from the car's current colour.

In each of the next $q$ days, before the day's journey starts, the driver will paint the car with any one colour even if car paints of that colour are not on sale in any garages in Byteland. Then he will drive from the $a$-th city to the $b$-th city without visiting any cities more than once.

To make the car more colourful to attract everyone's attention, the driver wonders the maximum times that he repaints the car in each day.

The first line contains two integers $n$ $(2\le n\le 200000)$ and $q$ $(1\le q\le 200000)$, indicating the number of cities in Byteland and the number of days of the chief test driver's journey in Byteland.
In each of the next $n$ lines, three integers $u$, $v$ $(1\le u,v\le n,u\ne v)$ and $k$ $(\ge 1)$ comes first, indicating that the $u$-th city and the $v$-th city is connected by a road, where the garage sells car paints of $k$ colours. Then $k$ distinct integers c1,c2,...,ckc_1, c_2, ..., c_kc1,c2,...,ck (1≤ci≤500000)(1 \le c_i \le 500\,000)(1≤ci≤500000) follows, indicating the colours of car paints sold by the garage. It is guaranteed that the sum of $k$ does not exceed $500000$.
Each of the next $q$ lines contains two integers $a$ and $b$ $(1\le a,b\le n,a\ne b)$, indicating a journey from the $a$-th city to the $b$-th city.

Output $q$ lines, each of which contains a single integer, indicating the maximum times of repainting the car during the journey from the $a$-th city to the $b$-th city.

5 5
1 2 4 4 5 9 2
1 4 1 4
2 3 1 2
4 5 1 2
5 3 5 2 9 6 5 4
5 2
2 3
2 4
1 3
1 5

3
4
3
3
3