Problem Description

Crosswords are popular among CyberAgent employees.

The crossword we are trying to create is a 2x2 grid where each of the 4 squares contains one letter. Each row read from left to right and each column read from top to bottom should form a word. Given the large number of letter types, in this problem, we assume that each letter corresponds to an integer.

You are given the number of letter types \( N \) and \( M \) words listed in the dictionary. Each letter is represented by an integer from 1 to \( N \). The dictionary consists of \( M \) lines, where the \( i \)-th line \( (1 \leq i \leq M) \) contains two integers \( a_i \) and \( b_i \). This means there is a word where the first letter is \( a_i \) and the second letter is \( b_i \). The same word does not appear multiple times in the dictionary.

Currently, the squares are empty, and you want to fill them such that each row and each column forms a word that exists in the dictionary. Calculate the total number of possible ways to fill the squares. Note that the same word can be used multiple times.

Input Format

The input is given in the following format:

\( N \) \( M \) \( a_1 \) \( b_1 \) : \( a_M \) \( b_M \)

Output Format

Output the total number of ways to fill the squares.

Sample Input and Output

Sample Input #1

3 4
1 2
2 1
3 1
2 3

Sample Output #1

5

Sample Input #2

4 10
1 1
1 2
1 3
2 1
2 2
2 4
3 3
3 4
4 1
4 3

Sample Output #2

47

Notes/Hints

Constraints

• \( 1 \leq N \leq 300 \)
• \( 1 \leq M \leq N \times N \)
• \( 1 \leq a_i, b_i \leq N \) \( (1 \leq i \leq M) \)
• \( (a_i, b_i) \neq (a_j, b_j) \) \( (1 \leq i < j \leq M) \)

Sample Explanation 1

There are 5 possible ways to fill the squares, as shown in the figure below.

见题面 Input 部分

见题面 Output 部分