cho.sh

해고

아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

찰리는 큰 회사의 인사 팀장이다. 이 회사에서 CEO를 뺀 모든 직원에게는 보고할 상사가 한 명 이상 있다. 직접이든 간접이든 자기 자신에게 보고하는 직원은 없다.

올해 예산이 나왔는데 인건비 항목이 CC달러 깎였다. 찰리는 사람을 자르는 일을 싫어해서, 보고할 상사가 한 명도 남지 않은 직원을 자동으로 해고하는 프로그램을 만들었다. 프로그램은 CEO 말고 보고할 상사가 없는 직원이 사라질 때까지 해고를 반복한다. CEO는 보고할 상사가 없어도 프로그램이 자동으로 해고하지 않는다.

찰리는 자기 손으로 딱 한 명만 해고하기로 했고, 나머지는 프로그램이 처리한다. 해고된 사람 전원의 급여 합은 CC달러 이상이어야 하고, 그러면서 CC에 최대한 가까워야 한다. 급여 합이 같은 선택이 여럿이면 사원 번호가 가장 큰 직원을 고른다. CEO가 무능할 수도 있으므로 찰리는 CEO를 해고해도 된다.

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다.

각 테스트 케이스의 첫 줄에는 직원 수 NN과 절감해야 하는 금액 CC가 주어진다.

이어지는 NN개의 줄은 00번부터 N−1N-1번까지의 직원을 순서대로 설명한다. ii번 직원의 줄에는 급여 SiS_i와 보고할 상사의 수 RiR_i가 먼저 오고, 그 뒤에 RiR_i개의 수 EijE_{ij}가 온다. EijE_{ij}는 ii번 직원이 보고하는 상사의 사원 번호다.

  • 1≤T≤1001 \le T \le 100
  • 1≤N≤2001 \le N \le 200
  • 1≤C≤∑iSi1 \le C \le \sum_i S_i
  • 1≤Si≤1000001 \le S_i \le 100000
  • 0≤Ri<N0 \le R_i < N이고, Ri=0R_i = 0인 직원은 정확히 한 명이다.
  • 0≤Eij<N0 \le E_{ij} < N

출력

각 테스트 케이스마다 찰리가 해고해야 하는 직원의 사원 번호를 한 줄에 하나씩 출력한다.