cho.sh

보안 게임

시간 제한2초메모리 제한512 MB

문제

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$