보안 게임

Albert는 "보안 게임" 이라는 보드 게임을 즐겨한다. 이 게임은 총 $N$ 개의 보안용 로봇을 적절히 활용하여 $M$ 개의 건물을 보호하는 것이 목표인데, 몇 가지 까다로운 규칙이 있다.

1. 각 로봇은 최대 $B$ 개의 다른 건물을 동시에 보호할 수 있다.
2. 각 로봇이 모든 건물을 보호할 수 있는 것은 아니고, $i$ 번째 로봇은 총 $g\_i$ 개의 다른 건물을 보호할 수 있는데, 보호 가능한 건물들을 $x\_{i, j}$로 나타내자 ($1 \le j \le g\_i$ 이고 $1 \le x\_{i, j} \le M$ 이다).
3. $k$ 번째 건물은 최소 $L\_k$ 대 그리고 최대 $U\_k$ 대의 다른 로봇을 통해 보호 되어야 한다 -- 이 때 각 건물의 점수는 해당 건물을 지키는 로봇의 수로 정해진다.
4. 위 규칙을 모두 지키면서 로봇을 배치하였다면 게임의 점수는 각 건물의 점수 총합이 된다. 만약 위 규칙을 모두 지키면서 로봇을 배치할 수 있는 방법이 없다면 게임의 점수는 -1 점이 된다.

편의상 $S\_b$ 는 $B = b$일 때 Albert가 얻을 수 있는 최대 게임 점수로 정의하자 ($1 \le B \le M$).

예를 들어 $N = M = 3$, $g = \[2, 2, 2]$, $x = \[\[1, 2], \[1, 3], \[2, 3]]$ 그리고 $L = \[1, 1, 1]$, $U = \[3, 3, 3]$ 이라 하자.

• 만약 $B = 1$ 이라면 다음 방법으로 최대 3점을 얻을 수 있다:
  • 로봇 1이 건물 2를 보호, 로봇 2가 건물 1을 보호, 로봇 3이 건물 3을 보호 -- 이 경우, 각 건물의 점수는 1점이고 게임의 점수는 3이다.
• 만약 $B = 2$ 이라면 다음 방법으로 최대 6점을 얻을 수 있다:
  • 로봇 1이 건물 1과 2를 보호, 로봇 2가 건물 1과 3을 보호, 로봇 3이 건물 2와 3을 보호 -- 이 경우, 각 건물의 점수는 2점이고 게임의 점수는 6이다.
• 만약 $B = 3$ 혹은 그 이상이더라도 6점보다 더 많은 점수를 얻을 방법은 없다. 따라서 $S = \[3, 6, 6]$ 이다.

다른 예로, $N = 4, M = 3$, $g = \[3, 1, 1, 1]$, $x = \[\[1, 2, 3], \[1], \[1], \[3]]$ 그리고 $L = \[1, 2, 1]$, $U = \[2, 2, 2]$ 이라 하자.

• 2번 건물의 경우 $L\_2 = U\_2 = 2$ 이므로 반드시 2대의 다른 로봇이 2번 건물을 보호해야한다.
• 하지만 2번 건물을 보호할 수 있는 로봇은 1번 뿐이므로, $B$의 값에 관계 없이 게임의 점수는 -1점이 된다.
• 이 경우 $S = \[-1, -1, -1]$ 이 된다.

입력으로 $N, M, g, x, L, U$가 주어졌을 때, $B$ 값에 따라 Albert가 얻을 수 있는 최대 점수를 구해보자 (즉, $S\_1, S\_2, \dots, S\_B$).

입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 $N, M$ 이 공백으로 구분되어 주어진다. 다음 $N$ 줄에 걸쳐 각 줄에는 $i$ 번째 로봇이 배치될 수 있는 건물의 수 $g\_i$ 와 함께 건물의 번호인 $g\_i$ 개의 정수가 ($x\_{i,1}, x\_{i, 2}, \dots, x\_{i, g\_i}$) 공백으로 구분되어 주어진다 (즉, 각 줄에는 $g\_i+1$ 개의 정수가 주어진다). 다음 $M$ 줄에 걸쳐 각 줄에 한 쌍의 정수 $L\_k, U\_k$ 가 주어지는데 이는 $k$ 번째 건물에 배치되어야 하는 최소/최대 로봇의 수를 나타낸다.

각 테스트 케이스의 정답인 $S\_1, S\_2, \dots, S\_M$ 을 공백으로 구분하여 각 줄에 출력한다.

• $1 \le T \le 10$

• $1 \le N, M \le 200$

• $\sum\_{1 \le i \le N} g\_i \le 5000$

• $1 \le i \le N$ 인 $i$에 대하여:

  • $1 \le g\_i \le M$
  • $1 \le x\_{i, 1}, x\_{i, 2}, \dots, x\_{i, g\_i} \le M$
  • $x\_{i, 1}, x\_{i, 2}, \dots, x\_{i, g\_i}$ 에 중복된 값은 없다

• $1 \le k \le M$ 인 $k$에 대하여: $1 \le L\_k \le U\_k \le N$