Team YouAreSoStrong meet a very boring problem. They have to schedule n jobs on m machines. Each job needs exactly one unit time on one machine. At first, YouAreSoStrong thought ceil(n/m) units of time is enough. Soon, they find out there exist some ordering constraints between jobs. This is reasonable. For example, you have to complete "hand in hand" before you can "hug". And only after you've done "hug", can you "kiss". It's guaranteed that following 3 conditions are satisfied.
1. one job can only be relied by at most one job.
2. one job may rely more than one job.
3.There is no circular dependency. Such as a relies on b, and b relies on a.
YouAreSoStrong thought for a long time, but do not have a clue. Can you help them?
First line contains one integer T, indicates the number of test cases. For each case, the first line contains 3 integers : n, e, m, denotes number of jobs, number of ordering constraints, number of machines separately. Each line from 2 to (e+1)th contains one pair of integers (a,b), which stands for job a must be done before job b can start. T≤10. 0 < n, e , m≤100 000.
Print one integer on one line for each case, which is the minimum units of time YouAreSoStrong can schedule all the jobs.