Description

When school goes on winter break, the informatics olympiad coach has $1,2,3,\cdots,x$ books to distribute to $x$ trainees. Each person can receive only one book, but each person has two favorite books.

The teacher first asks each person to write down the books they like on a sheet. Then, based on these sheets, the teacher assigns the books. Please write a program to find the total number of possible assignment schemes in which every student is satisfied.

Input Format

Line $1$: a number $x$.

Lines $2$ through $1+x$: each line contains two numbers, indicating the indices of the books that $a_i$ likes.

Output Format

A single number: the total number of schemes $\mathit{total}$.

5
1 3
4 5
2 5
1 4
3 5

2

Hint

Constraints

For all testdata, $1\le x\le 20$.

$\text{update 2022/03/07}$, Ruan Xingzhi

In the original testdata for this problem, the last data point has $x$ equal to $0$, and the expected output is $0$. Considering this data is unreasonable, it has been removed. Now, when submitting this problem, you will not encounter data points with $x=0$.

Translated by ChatGPT 5