시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 0 0 0 0.000%

문제

우주 최고의 프로그래머 교준이는 $N$명의 학생을 데리고 "최강의 PS 군단"을 만들고자 한다.

$N$명의 학생 중에는 같이 있을 때 시너지 효과가 발생하는 학생 조합이 있다. $i$번 학생의 "시너지 동료" 집합을 $A_i$라 하자. 이는, $i$번 학생은, 모든 $j \in A_i$에 대하여, 자신이 $j$번 학생과 같이 있을 때 시너지 효과가 나온다고 생각함을 의미한다. 반대로, $j \not \in A_i$라면, $i$번 학생은 자신이 $j$번 학생과 같이 있어도 시너지 효과가 나온다고 생각하지 않음을 의미한다. $(0 \le i \le N-1)$

교준이가 생각하는 "최강의 PS 군단"의 조건은 꽤 까다롭다. $N$명의 학생이 다음 조건을 모두 만족할 때, 교준이는 "이 $N$명의 학생이 최강의 PS 군단을 이룬다''고 말한다:

  • $i$번 학생이 $j$번 학생의 "시너지 동료"라면, $j$번 학생 또한 $i$번 학생의 "시너지 동료"라야 한다$(0 \le i \le N-1, 0 \le j \le N-1)$.
  • 다음 조건을 모두 만족하도록 $N$명의 학생을 하나 혹은 여러 개의 그룹으로 나눌 수 있다:
    • 각 학생은 정확히 하나의 그룹에 속한다.
    • 각 그룹에 속한 학생의 수는 $1$ 이상 $B$ 이하다.
    • 자신과 다른 그룹에 속한 "시너지 동료"를 "외부 시너지 동료"라고 하자. 각 그룹에 대하여, 그 그룹에 속한 학생의 "외부 시너지 동료"의 수의 합은 $C$ 이하다.

$N$명의 학생은 교준이에게 있어 "최강의 PS 군단"인지 판별하는 프로그램을 작성하시오.

입력

첫 번째 줄에 세 정수 $N$, $B$, $C$가 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐, $N$명의 학생의 "시너지 동료"에 대한 정보가 주어진다.

$(i+2)$번째 줄에는 정수 $|A_i|$와, 집합 $A_i$에 속한 $|A_i|$개의 정수가 주어진다 $(0 \le i \le N - 1)$.

출력

만약, $N$명의 학생이 "최강의 PS 군단"을 이루지 않는다면, 첫 번째 줄에 "NO(따옴표 제외)를 출력한다.

만일, $N$명의 학생이 "최강의 PS 군단"을 이룬다면, 첫 번째 줄에 "YES"(따옴표 제외)를 출력한다. 여기서, $K$개의 집합 $P_1, P_2, \cdots, P_K$가 다음 조건을 모두 만족한다고 하자:

  • $1 \le K \le N$
  • $P_1 \cup P_2 \cup \cdots \cup P_K = \{ 0, 1, \cdots, N-1 \}$
  • $P_i \cap P_j = \emptyset$ $(1 \le i < j \le K)$
  •  $1 \le | P_i | \le B$ $(1 \le i \le K)$
  • $\displaystyle \sum_{p \in P_i} \left| A_p \setminus P_i \right| \le C$ $(1 \le i \le K)$

계속하여, 두 번째 줄에는 정수 $K$를 출력한다.

또한, 세 번째 줄부터 $K$개의 줄에 걸쳐, $K$개의 집합 $P_1, P_2, \cdots, P_K$애 대한 정보를 출력한다. $(i+2)$번째 줄에는 정수 $| P_i |$와, 집합 $P_i$에 속한 $| P_i |$개의 정수를 오름차순으로 차례대로 출력한다 $(1 \le i \le K)$.

위와 같은 조건을 만족하는 $(K, P_1, P_2, \cdots, P_K)$가 여러 가지라면, 그 중 아무거나 하나를 취해도 정답으로 인정된다.

제한

  • $1 \le N \le 2\,500$
  • $0 \le B$
  • $0 \le C$
  • $B+C \le 15$
  • $|A_0| + |A_1| + \cdots + |A_{N-1}| \le 30\,000$
  • 집합 $A_i$에 속한 원소는 서로 다르다. $(0 \le i \le N-1)$
  • 집합 $A_i$에 속한 원소는 모두 $0$ 이상 $N-1$ 이하다. $(0 \le i \le N-1)$
  • $i \not \in A_i$ $(0 \le i \le N-1)$

예제 입력 1

1 0 1
0

예제 출력 1

NO

예제 입력 2

1 1 0
0

예제 출력 2

YES
1
1 0

예제 입력 3

2 1 1
1 1
1 0

예제 출력 3

YES
2
1 1
1 0

예제 입력 4

4 2 2
3 1 2 3
1 0
2 0 3
2 2 0

예제 출력 4

YES
2
2 0 1
2 2 3

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2017 G번

  • 문제를 번역한 사람: yclock