405967: GYM102192 G 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 ≤ T ≤ 50), the number of test cases.

Each test case begins with a single line of integer n (1 ≤ n ≤ 10⁵), 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 ≤ x, y ≤ 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⁶.

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.

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.