ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

УрКОП 2020

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. 4B and Zoo

Time limit: 1.0 second
Memory limit: 256 MB
The 4B class went to a zoo with their teacher. Unfortunately for her, there’s a lot of children, and she’s alone. To make it easier for herself, she decided to separate children into groups of 2 or 3 students. Each student may only be assigned to one group! However, this is difficult, because each child will only want to be in a group with someone they know.
There are n students in the 4B class. The teacher knows which students are friends (the friendship is always bidirectional!) and that each student is a friend of at least ⌈n2⌉ other students (⌈x⌉  is the smallest integer that is greater than or equal to x). Help the teacher to separate children into groups.


The first line contains a single integer n (2 ≤ n ≤ 1000).
Each of the next n lines contains space-separated integers mi, 1, mi, 2, …, mi, n. These integers are all either 0 or 1 (mi, j ∈ {0, 1}). If mi, j = 1, then i-th and j-th students are friends, otherwise they aren’t. It is guaranteed that mi, j = mj, i and mi, i = 0.


In the first line, write “YES” (without quotes) if the students can be separated into groups, otherwise output “NO”. In the case of “NO” nothing else needs to be written.
In the second line, write k — the number of groups.
Then output k more lines, i-th of them should start with ai — the size of the i-th group. Then write ai integers in the same line — indices of students in the i-th group. The students are numbered from 1 to n in the same order they are given in the input.


0 1
1 0
2 1 2
0 1 0 1 1
1 0 1 0 1
0 1 0 1 1
1 0 1 0 1
1 1 1 1 0
3 1 2 5 
2 3 4
Problem Author: Semyon Trifochkin
Problem Source: Ural School Programming Contest 2020
To submit the solution for this problem go to the Problem set: 2150. 4B and Zoo