Card Game

Problem Source

HDU 6403

Problem Description

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

• Alice arranges the cards in a row, and for each card she chooses one of its faces to place face up;
• Bob turns over the minimum number of cards so that all numbers on the face-up faces become unique.

They play the game several times, and Bob always succeeds in making the numbers unique. However, neither of them is sure whether the number of cards flipped is minimal. Moreover, they want to figure out the number of different ways to flip the 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!

Input Format

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 integer $n$ ($1 \leq n \leq 10^5$), the number of cards on the table. Then follow $n$ lines specifying the cards 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$.

Output Format

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 -1 -1 instead.

Sample Input

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

Sample Output

2 4
-1 -1
0 1

Hint

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 cannot be done with fewer 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.