Card Game

Alice and Bob are playing a card game. In this card game, a number is written on each face of the playing card. The rule of the game is described as follows:

- Alice arranges the cards in a row, and for each of the cards, she chooses one of its faces to place it up;
- Bob turns over minimum number of cards to make all numbers on the front faces unique.

They play the game some times, and Bob always succeeds making the numbers unique. However, both of them are not sure whether the number of cards flipped is minimum. Moreover, they want to figure out the number of different ways of turning over minimum number of cards to make the numbers unique. Two ways are considered equal if and only if the sets of flipped cards are equal. Please write a program to help them!

The first line of the input is a single integer $T$ $(1 \leq T \leq 50)$, the number of test cases.

Each test case begins with a single line of integer $n$ $(1 \leq n \leq 10^5)$, the number of cards on the table. Then follow $n$ lines, specifying the cards that Alice arranges. Each of these $n$ lines contains two integers $x, y$ $(1 \leq x, y \leq 2n)$, meaning that Alice places a card with number $x$ on the front face and number $y$ on the back face.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

For each test case, display two integers in a line, the minimum number of cards to turn over, and the number of different ways of flipping modulo $998244353$, respectively. If it is impossible to turn over cards to make all numbers unique, display $\texttt{-1 -1}$ instead.

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

2 4
-1 -1
0 1

In the first sample test case, Bob may turn over one of the first two cards and one of the last two cards, so there are four different ways of turning over two cards to
make all numbers on the front faces unique. Obviously, this can't be done with less than two cards flipped.

In the second sample test case, it is impossible to make all numbers on the front faces unique.

In the third sample test case, all numbers on the front faces are already distinct.

2018 Multi-University Training Contest 8