Group Partitioning with Constraints

You are given a school with \( n \) students numbered from 1 to \( n \). Their friendship relation is symmetric; that is, if student \( a \) is a friend of student \( b \), then student \( b \) is also a friend of student \( a \).

The friendship network is provided as \( m \) pairs. You are also given two integers \( p \) and \( q \). The students must be partitioned into groups satisfying the following conditions:

• Each student belongs to exactly one group.
• The size of each group is at least 1 and at most \( p \).
• For every group \( G \), let the cross-group friend count be defined as the number of friendship pairs \( (u,v) \) such that \( u \in G \) and \( v \notin G \) (each pair is counted in both groups it touches). This number must be at most \( q \) for each group.

If there exists a partition satisfying all the conditions, output one valid grouping. Otherwise, output -1 to indicate that the given constraints cannot be satisfied.

Note: In a valid grouping, every friendship between students in the same group does not contribute to the cross-group friend count.

inputFormat

The input is given as follows:

 n m p q
 a1 b1
 a2 b2
 ...
 am bm

• The first line contains four integers \( n \), \( m \), \( p \), and \( q \) where \( 1 \le n \le 20 \) (you may assume small \( n \) for this problem), \( m \) is the number of friendship pairs, \( 1 \le p \le n \), and \( q \ge 0 \).
• Each of the next \( m \) lines contains two integers \( a_i \) and \( b_i \) (\( 1 \le a_i, b_i \le n \) and \( a_i \ne b_i \)) indicating that student \( a_i \) and student \( b_i \) are friends.

outputFormat

If a valid grouping exists, output the grouping in the following format:

 k
 s1 v11 v12 ... v1,s1
 s2 v21 v22 ... v2,s2
 ...
 sk vk1 vk2 ... vk,sk

where \( k \) is the number of groups, and for each group, the first number is its size followed by the list of students in that group. If no valid grouping exists, output -1.

sample

3 2 3 1
1 2
2 3

1
3 1 2 3