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 days.

Byteland has cities numbered from to , and 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 paint of some colours on each road. Every time when the driver passes through a road, he will choose one colour of car paint from the garage and repaint the car if that colour is different from the car's current colour.

In each of the next 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 -th city to the -th city without visiting any cities more than once.

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

The first line contains two integers   and  , 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  lines, three integers ,   and   comes first, indicating that the -th city and the -th city is connected by a road, where the garage sells car paints of  colours. Then  distinct integers   follow, indicating the colours of car paints sold by the garage. It is guaranteed that the sum of  does not exceed .

Each of the next  lines contains two integers  and  , indicating a journey from the -th city to the -th city.

Output  lines, each of which contains a single integer, indicating the maximum times of repainting the car during the journey from the -th city to the -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

8 7
1 2 2 4 1
1 4 3 4 1 2
1 5 3 1 2 4
1 7 1 4
2 3 1 1
3 4 3 1 2 4
4 6 1 1
7 8 1 2
8 7
4 1
2 3
4 7
4 8
5 8
1 8

1
3
3
3
4
3
2