Floating Formation

Industrial design students decided to show their pieces floating on the water of the IJsselmeer. The pieces do not stay afloat by themselves, so the students took a few boats and tied the pieces together with them.

A boat has one rope connection point on its left side and one on its right side, so a boat is tied to at most two pieces. A piece tied to two or more boats keeps floating. A piece tied to only one boat does not float properly. The part furthest from the boat dips into the water and soaks, the piece gets heavier, and in the end it sinks. The boat tied to a sunken piece unties itself from the piece on its other side and carries the soaked piece back to the beach. The students want that boat to stay tied to the soaked piece, so it never comes back to the water. The piece it left behind loses one supporting boat, and it can start to sink for the same reason. A piece stays afloat only while at least two boats are tied to it.

There are simple ways to tie the pieces so that nothing sinks, for example joining the pieces and the boats into one circle. The students did not do that. Their arrangement is a single connected component, but many pieces hang on one boat and are in danger of sinking. Every boat that the students used is tied to two different pieces, and no boat is tied to just one piece.

The students admitted the mistake and asked you to save as many pieces as you can with the spare boats they have left. You may not change the current arrangement. On top of that, you may use only the left connection point of a spare boat, so that the order in which the boats sit does not change. A spare boat is therefore tied to exactly one piece. You do not have to use every spare boat, and you may tie several spare boats to the same piece.

Report how many pieces sink in the end when the spare boats are used as well as possible.

The first line has one positive integer, the number of test cases, at most 100. Each test case is given as follows.

• One line with three space separated integers $n$, $m$ and $k$ ($1 \le n, m, k \le 10000$): the number of pieces, the number of boats already used, and the number of spare boats.
• $m$ lines, each with two space separated integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$): a boat is tied to piece $a$ on its left side and to piece $b$ on its right side.

No two boats are tied to the same pair of pieces. The pieces and the boats form a single connected component, and the arrangement is not guaranteed to be planar. At least one piece stays afloat even when no spare boat is used.

For each test case, print one line with a single integer: the smallest number of pieces that sink in the end when the spare boats are used as well as possible.