岛国的火车票

Time Limit: 2000MS

Memory Limit: 131070Kb

Description

岛国是一个狭长的国家,由于国家的人数越来越多,所以他们开始不断的和邻国发生争议,想要将天朝的钓鱼岛国有化,骗取棒子的独岛……额,扯远了……言归正传,在岛国,只有一条铁路干线,而火车在每段路上的载客人数又是固定的,因此对火车票管理系统的要求也越来越高,现在他们在完成一个新的系统,实现以下功能:采用先来先服务的方式,对于每个来买票的人,尽可能的多给他想要的票(每个人买的票不超过10张,以每张票的起点、终点表示这张票),有多种方式可以达到最大张数时,输出字典最小的方案(见样例说明)。

Input

第一行一个整数case(case<=20),表示测试数据的组数。

对于每组测试数据第一行三个整数N,K,Q。(N表示火车站的个数,标号从1到N。K表示每段路上的载客最大值,Q表示来买票的人数)接下来Q部分,每部分第一行一个整数m,表示当前这个人要买的票数,接下来m对数,每对数a,b表示有一张票是从a站到b站。

(N<=50000,K<=100,Q<=1000,m<=10,1<=a<b<=N)

Output

对于每个来买票的人,输出两行,第一行一个整数w,表示他最多可以买到的火车票张数,第二行w对数,形如(A1,B1)(A2,B2)...(Aw,Bw),如果w为0,直接输出空行。

Sample Input

1
10 2 3
3
1 5
3 6
2 7
1
3 7
1
6 10

Sample Output

2
(1 5)(2 7)
0

1
(6 10)

Hint

对于第一个来买票的人,最多可以给他两张票,可以有两种方案,(1 5)(3 6) 和(1 5)(2 7),字典序的比较是两种方案的每张票依次比较过去,先比较起点,若起点相同再比较终点。因此后者字典序较小,所以输出后者。

Source

张俊杰

提交代码