34050번 - 타일 깔기 스페셜 저지

문제

$N$행 $M$열 크기의 직사각형 바닥에 타일을 깔려고 한다. 초기에는 타일이 어디에도 깔려있지 않으며 각 행마다 $T$개의 타일 세트 중 하나를 사용할 수 있다. $i$번째 타일 세트는 $k_i$개의 수 $x_{i,1},ドル $x_{i,2},ドル $\cdots,ドル $x_{i,k_i}$로 나타낼 수 있으며 이는 $h$행에 $i$번째 타일 세트를 사용한 경우 $h$행 $x_{i,1},ドル $x_{i,2},ドル $\cdots,ドル $x_{i,k_i}$열에 타일이 깔림을 나타낸다.

타일 세트의 목록이 주어질 때 다음 조건을 만족하는 $a+b$개의 정수 순서쌍 $(r_{1,1}, c_{1,1}),ドル $(r_{1,2}, c_{1,2}),ドル $\cdots,ドル $(r_{1,a}, c_{1,a}),ドル $(r_{2,1}, c_{2,1}),ドル $(r_{2,2}, c_{2,2}),ドル $\cdots,ドル $(r_{2,b}, c_{2,b})$가 존재하도록 타일을 까는것이 가능한지 판별하고 가능하다면 그 방법을 하나 찾아보자.

• $r_{1,1}<r_{1,2}<\cdots<r_{1,a}$ 이며 $c_{1,1}<c_{1,2}<\cdots<c_{1,a}$ 이고 1ドル \leq i \leq a$인 모든 $i$에 대해 $r_{1,i}$행 $c_{1,i}$열에 타일이 깔려있다.
• $r_{2,1}<r_{2,2}<\cdots<r_{2,b}$ 이며 $c_{2,1}>c_{2,2}>\cdots>c_{2,b}$ 이고 1ドル \leq i \leq b$인 모든 $i$에 대해 $r_{2,i}$행 $c_{2,i}$열에 타일이 깔려있다.

입력

첫 번째 줄에 $N,ドル $M,ドル $T,ドル $a,ドル $b$가 공백으로 구분되어 주어진다. $(1\leq N,M,T \leq 5000; 1\leq a,b \leq \min(N,M))$

다음 $T$개의 줄에 걸쳐 타일 세트에 대한 정보가 주어진다. $i+1$번째 줄에는 $i$번째 타일 세트가 채우는 열의 개수 $k_i$와 $k_i$개의 열 인덱스 $x_{i,1},ドル $x_{i,2},ドル $\cdots,ドル $x_{i,k_i}$가 공백으로 구분되어 주어진다. $(1\leq \sum k_i \leq 5000; 1\leq x_{i,j} \leq M; x_{i,j_1} \neq x_{i,j_2})$

각 열은 최소 하나의 타일 세트에 포함된다. 즉, 1ドル\leq k \leq M$인 모든 정수 $k$에 대해 $x_{i,j}=k$를 만족하는 $i,j$가 존재한다.

출력

조건을 만족하도록 타일을 까는것이 불가능하다면 No를 출력한다.

그렇지 않다면 Yes를 출력하고 다음 줄에 사용한 타일 세트의 번호를 나타내는 $N$개의 정수 $p_1,ドル $p_2,ドル $\cdots,ドル $p_N$을 공백으로 구분해 출력한다. 이는 $i$번째 행에 $p_i$번째 타일 세트를 사용했음을 나타낸다. $(1 \leq p_i \leq T)$

제한

힌트