Book Allocation Problem

During the winter break, a teacher has \(1, 2, 3, \cdots, x\) books to distribute among \(x\) students. Each student may only receive one book and each student has exactly two favorite books. Prior to the distribution, every student submits a list containing his/her two favorite books. The teacher now wants to assign one book to each student such that every student receives one of his/her favorite books.

Your task is to write a program that calculates the number of possible assignment schemes that satisfy the above requirement.

Note: Books are labeled from 1 to \(x\). Each student specifies two distinct integers indicating his/her favorite books.

inputFormat

The first line contains an integer \(x\) (\(1 \le x \le 20\)) indicating the number of students and books. Each of the following \(x\) lines contains two distinct integers, representing the two favorite books for that student. It is guaranteed that the book numbers lie between 1 and \(x\) (inclusive).

outputFormat

Output a single integer: the total number of valid book assignment schemes such that every student gets one of his/her favorite books.

sample

3
1 2
2 3
1 3

2