Smugglers vs Detectives

The detectives from law enforcement company Catch&Jail Ltd. investigate a group of smugglers. The detectives compiled an investigation list of these individuals. Before they crack down on the suspects they want to extract as much knowledge as possible from the information already available to the company.
A new criminal syndicate operates in the area and their people are organized into so called packs. The detectives are sure there are members of two packs in their list of suspects.

The following information is known to the detectives.

Identity of pack structure.
Let there be two packs. Whenever members of one pack are listed in an arbitrary but fixed order then the members of the other pack can be listed in such order that the following is true:

The detectives hope they can identify two packs in their list of suspects. However, because of the incomplete knowledge, they first need to produce a set of all possible pairs of packs in their investigation list.


Figure 1. Schemes of connections between pairs of suspects in the investigation list. In case a), the list contains 8 individuals with 9 connections between some of them. In case b), the list contains 14 individuals with 19 connections between some of them. The smaller highlighted schemes, in each of the cases, present all possible pairs of packs in the given list. The members of the packs are shown as black dots and the connections between them are shown as thick lines. The values of P and C, respectively, are 3 and 2 in case a) and 4 and 4 in case b). The schemes correspond to Examples 1 and 2 below.

The task

You are given a list of all pairs of smugglers who are mutually connected. Also, you are given the size of the smugglers pack and the number of connections in a pack. Determine all possible pairs of packs in the given list.


Input

The first input line contains four positive integers N, M, P, C, where N is the number of smugglers in the list, M is the number of connections in the list, P is the pack size and C is the number of connections in a pack. For simplicity, the smugglers are labeled 0, 1, 2, ..., N−1.
Next, there are M input lines, each line represents one connection between two smugglers. The connection is listed as a pair of integers separated by space, the integers represent the labels of the smugglers in the pair.
The list of connections and also each particular connection are given in arbitrary order.
The following limits hold: 4 ≤ N ≤ 30, N−1 ≤ M ≤ 100, 3 ≤ P ≤ 7, 3 ≤ C ≤ 10,

Output

The output contains one or more text lines. Each line contains a possible pair of packs in the investigation list.
The pack which contains the member with the lowest label is listed first on the line, the other pack follows. A list of a pack is a sequence of the labels of its members sorted in ascending order.
The values on a line are separated by spaces. The lines are sorted in ascending lexicographical order.
There is always at least one possible pair of packs in the investigation list. The number of possible pair of packs is at most 5000.

Example 1

Input
8 9 3 2
0 1
0 2
1 2
2 3 
3 4
4 5
5 6
6 7
7 3
Output
0 2 3 4 5 6
0 2 3 5 6 7
1 2 3 4 5 6
1 2 3 5 6 7
2 3 4 5 6 7
2 3 7 4 5 6
The data of Example 1 is depicted in Figure 1a).

Example 2

Input
14 19 4 4
0 1
0 5
1 5
2 3
2 7
3 7
4 5
5 6
6 7
7 8
9 10
10 11
11 12
12 13
4 9
5 10
6 11
7 12
8 13
Output
0 1 4 5 2 3 6 7
0 1 4 5 2 3 7 8
0 1 4 5 2 3 7 12
0 1 5 6 2 3 7 8
0 1 5 6 2 3 7 12
0 1 5 10 2 3 6 7
0 1 5 10 2 3 7 8
0 1 5 10 2 3 7 12
4 5 9 10 6 7 11 12
4 5 9 10 7 8 12 13
5 6 10 11 7 8 12 13
The data of Example 2 is depicted in Figure 1b).

Example 3

Input
6 15 3 3
0 1
0 2
0 3
0 4
0 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Output
0 1 2 3 4 5
0 1 3 2 4 5
0 1 4 2 3 5
0 1 5 2 3 4
0 2 3 1 4 5
0 2 4 1 3 5
0 2 5 1 3 4
0 3 4 1 2 5
0 3 5 1 2 4
0 4 5 1 2 3

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to the public data set