F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Card Game

Time Limit: 3000/3000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 898    Accepted Submission(s): 271


Problem Description
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!
 

Input
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$.
 

Output
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.
 

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

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 03:53:42, Gzip enabled