Server Time: Wed Mar 20, 2019 8:58 am
Welcome ( logout
1390 - Weight Comparison
  PDF (English) Statistics Forum
Time Limit: 4 second(s) Memory Limit: 32 MB

Rimi has n different objects having distinct weights and identified by x1, x2, ..., xn. All she wanted to do is to sort them in ascending order according to their weights. That's why she asked her robot-helper to do all the weight comparisons. She went for another task, and the robot continued doing the comparisons. This robot was not that intelligent, that's why it was picking two objects randomly, compared them and wrote down the object names as xi xj meaning that xi is heavier than xj. After a while, Rimi came back and found this foolishness of the robot. So, she wants to find the comparisons that are really necessary. For example, the robot compared and found the following:

1.       x1 > x2

2.      x2 > x5

3.      x1 > x5

Clearly the third one is unnecessary, as from the first two relations, it's clear that x1 is heavier than x5. But the second one is necessary since from first and third relation, it's impossible to determine the relation between x2 and x5. The first relation is also necessary. Now Rimi wants to keep minimum number of necessary relations such that they are enough to find all the comparisons.


Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a blank line. Next line contains two integers n, m (1 ≤ n ≤ 5000, 0 ≤ m ≤ 105), where m denotes the number of comparisons done by the robot. Each of the next m lines contains two integers i j (1 ≤ i, j ≤ n, i ≠ j) meaning that xi is heavier than xj. There is no duplicate transition. And assume that the data is valid.


For each case, print the case number and the number of necessary comparisons. Then print the comparisons in i j (xi is heavier than xj) form, first sorted by i then by j in ascending order.

Sample Input

Output for Sample Input



4 4

1 2

3 4

2 3

1 4


4 1

4 2

Case 1: 3

1 2

2 3

3 4

Case 2: 1

4 2


Dataset is huge; use faster I/O methods.

Problem Setter: Jane Alam Jan
Special Thanks: Muhammad Rifayat Samee
Developed and Maintained by
Copyright © 2012
LightOJ, Jane Alam Jan