407361: GYM102770 I Invoking the Magic

BaoBao is a lazy boy. He has $$$n$$$ pairs of socks in different colours and he washes them once a month. In the washing machine, these socks will be mixed.

Because there are too many socks that need to be paired, BaoBao divides the whole sock pairing process into two stages.

In the first stage, BaoBao randomly distributes the socks in pairs. Then in the second stage, BaoBao repeats the following operation until all the socks are paired: BaoBao chooses some of the pairs of socks, puts them into his magic washing basin, and uses his magic. If the socks in the magic washing basin can be paired perfectly when he uses his magic, the magic washing basin will pair them for BaoBao automatically. However, if they can't (which means there is at least one sock whose colour is unique in the basin), the magic basin will explode and BaoBao must not let this happen.

BaoBao's magic is limited, after the first stage, he needs to know the minimum capacity of the magic washing basin that he needs to pair all the socks successfully. The capacity of the basin is the maximum number of pairs of socks BaoBao can put in the magic washing basin at one time.

The input contains multiple cases. The first line of the input contains a single positive integer $$$T$$$ ($$$1 \le T \le 10$$$), the number of cases.

For each case, the first line of the input contains a single integer $$$n \ (1 \le n \le 10^5)$$$, the number of pairs of socks.

For the following $$$n$$$ lines, the $$$i$$$-th ($$$1 \le i \le n$$$) line contains two integers $$$a_i$$$ and $$$b_i$$$ $$$(1 \le a_i, b_i \le 2^{30})$$$, denoting the colours of the two socks in the $$$i$$$-th pair after the first stage. It is guaranteed that for each sock, there is exactly one other sock of the same colour.

For each case, print a single line containing a single integer, the minimum capacity of the magic washing basin.

1
5
1 2
2 3
1 3
4 5
4 5

3

In the sample, BaoBao can first put these three pairs of socks: {1,2}{2,3}{1,3} in the magic washing basin and then they will be paired into {1,1}{2,2}{3,3}. Then, he can put {4,5}{4,5} in the magic washing basin and they will be paired into {4,4}{5,5}. Therefore, with a capacity of $$$3$$$ it is possible to pair all the socks successfully. It can be shown by brute-force that this is impossible with a capacity of $$$2$$$.