1 人解决，1 人已尝试。
5 份提交通过，共有 5 份提交。
8.9 EMB 奖励。
单点时限: 20.0 sec
内存限制: 256 MB
Banana Immobile2, the newest star on the cellular sky, is starting to provide a new service. First, they collected statistics of the calls made by their customers during a few months and noted which pairs communicated very often. Then, they started offering the Happy Packs.
When a customer buys a Happy Pack, he is presented with a list of phone numbers he called or was called from during the last month. He may now mark at most K of these phone numbers as his “Happy numbers”. Making a call to a Happy number will then cost him absolutely nothing! One person can even buy more than one Happy Pack and mark up to K new phone numbers for each Happy Pack bought. Wonderful, isn’t it?
A group of students who would spend hours on the phone (if they had the money to pay the bills) learned about this new service from the local newspaper. They started spinning a plan immediately: Suppose that you could choose two Happy numbers for each Happy Pack and that Henry and Alice bought one each. Henry would then specify Oscar’s and Chad’s numbers as his Happy ones, while Alice would choose Patricia’s and Chad’s. Then Patricia could call Oscar free of charge!
How’s that possible? All their phones are able to arrange conference calls. In other words, each phone is able to take two phone calls it participates in, and merge them into one larger call where every participant of both original calls can hear all the other participants.
In our example Patricia could start by ringing Alice. Alice does not pick up the call (as this would cost Patricia some money). Instead, Alice calls her back, and Patricia explains that she needs to talk to Oscar. Alice calls Chad and merges the two calls. So now Patricia, Alice and Chad are having a conference call. Chad rings Henry, Henry calls Chad back, Chad merges the two calls he takes part in. Henry calls Oscar and merges the two calls together. Now all five friends share the same call and Patricia can (finally!) talk to Oscar for free.
Simple, isn’t it? Unfortunately, these five friends belong to a much bigger group. Figuring out who needs to buy the Happy Pack (and how many of them) and choosing the Happy numbers is a very difficult task, so they’d like to ask you for help.
Given is a group of friends. For each of them, you know the list of numbers that are eligible to be his Happy numbers. Find the least number of Happy Packs they need to buy so that all of them can call each other for free. You also have to provide one optimal way of achieving their goal. You can assume that the problem has at least one solution.
The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.
The first line of each test case contains three integers, N and M, and K, where N is the number of friends, M is explained below, and K specifies how many Happy numbers you get in one Happy Pack.
For simplicity we will assume that the friends are numbered from 1 to N. The next M lines of the test case contain two integers A and B each. These numbers denote that one of the friends A and B called the other at least once during the last month. This means that A can pick B’s number and also that B can pick A’s number as her Happy number.
For each of the test cases, the output shall consist of multiple lines. Each line with the exception of the last one should contain two integers, A and B specifying that person A should choose person B’s phone number as his or her Happy number. The last line should contain two zeroes.
Note that the number of Happy Packs necessary can be easily computed from your output data. Your only goal is to minimize the number of the Happy Packs. If there are more ways to achieve this goal you may print an arbitrary one. The pairs in the output don’t have to be sorted in any way, and their count does not have to be minimal (as shown in the second test case in the example). Although it doesn’t make much sense, you can include the same pair multiple times in the output. Be aware that each such occurence will be counted separately (and might increase the number of Happy Packs undesirably).
2 5 4 2 1 2 4 5 3 2 3 4 5 6 3 1 2 1 3 1 4 4 5 2 3 3 5
2 1 2 3 4 5 4 3 0 0 1 2 1 3 1 4 3 1 3 2 3 5 0 0
1 人解决，1 人已尝试。
5 份提交通过，共有 5 份提交。
8.9 EMB 奖励。