Problem D. Dense schedule ≡

Statement

One famous university has failed to create a proper schedule of classes before the beginning of the academic year. Teachers decided to fix this. They created a list of classes that teachers have to give to some of the groups of students according to the academic plan. However, coming up with an actual schedule is difficult and feels like something that a computer can do. They came to computer science department and asked you to write a program that will generate the best schedule.

There are N teachers numbered from 1 to N. There are M groups of students numbered from 1 to M. Teachers created a list of K pairs (t, g), meaning that teacher t needs to give a class to a group g. Some pairs may repeat in the list — this is because there might be several classes per day for the same subject (e.g., Calculus).

For simplicity, suppose that all these classes should happen in one day. The length of each class is the same and equal to the length of academic "pair" — a time slot. Of course, a teacher can not give two classes at the same time, as well as a group can not attend two classes simultaneously.

The best schedule is the one that fits into the minimum number of time slots. In other words, the schedule should ensure that the last teacher and the last group of students will leave the university as soon as possible.

Input file format

Input file contains integers N, M, K, followed by K pairs of integers t_i and g_i.

Output file format

Output file must start with an integer — the number of time slots in the schedule, followed by time slots description. Each description starts with l_i — the number of classes happening in this time slot, followed by (t, g) pairs from the original list.

The output must list all pairs from the input (∑l_i = K).

Constraints

1 ≤ N, M ≤ 100; 1 ≤ K ≤ 1000

1 ≤ t_i ≤ N; 1 ≤ g_i ≤ M

Sample tests

1 3 2
1 1
1 2

2
1
1 1
1
1 2

2 2 4
1 1
1 2
2 1
2 2

2
2
1 1
2 2
2
1 2
2 1