An online one-on-one competitive game called "Icing" is popular among many middle and high school students. The game company has expanded this game to develop "Icing II," a team-play-only version where matches can be held between Team I and Team Sing. Icing II is designed to form teams in a unique way by utilizing the gamers' existing match history from Icing. Specifically, two gamers who have played a one-on-one match in Icing must belong to different teams. Each team must have at least one member, and the number of members in the two teams can be different.

For example, the following shows an example of forming teams for Icing II using the match history of four gamers A, B, C, and D in Icing.

Icing Match History: A-B, A-C, B-D, C-D Icing II: Team I: A, D; Team Sing: B, C

However, a critical problem was discovered just 3 minutes before the Icing II server opens. For example, if gamers A, B, and C have all played against each other, they must all be on different teams, making it impossible to form Team I and Team Sing. To solve this problem, the following solution is to be applied: remove the minimum number of match records from the Icing match history. For example, consider the case where the one-on-one match records of four gamers A, B, C, and D are given: A-B, A-C, A-D, B-C. In this case, at least one record must be removed, and if the record A-B is removed, it is possible to form two teams (Team I: A, B; Team Sing: C, D).

As another example, consider the following match history: A-B, A-C, A-D, B-C, B-D, C-D. In this case, at least two match records must be removed, and if A-B and C-D are removed, two teams can be formed as follows (Team I: A, B; Team Sing: C, D).

However, because there are only 3 minutes left until the game launch, the number of records that can be removed is limited to a maximum of two. If more than 3 records need to be removed, it might be better to delay the launch.

In the meantime, the CEO of the game company became curious about how many different sets of match records of the minimum size can be removed to form two teams. That is, if the minimum number of match records to be removed is $K$, you need to count the number of subsets of match records of size $K$ that can be removed. In the second example, if you remove {A-B}, {A-C}, or {B-C}, you can form two teams while removing the minimum number of match records. The answer in this case is 3. In the third example, if you remove {A-B, C-D}, {A-C, B-D}, or {A-D, B-C}, you can form two teams while removing the minimum number of match records. The answer in this case is 3.

You must implement the following function to find the number of different ways to select the minimum number of match records to remove so that two teams can be formed using the given Icing match history. The order of selecting the match records to remove does not matter. Also, if it is impossible to proceed with the game by removing 2 or fewer match records, return 0. If there is no need to remove any records, the number of ways is 1, as doing nothing is the fastest and only way.

long long count_ways( int N, vector<int> U, vector<int> V ) ;

$N$ is the number of gamers, and $U$ and $V$ are vectors of size $M$ where an Icing match record exists between $U_i$ and $V_i$. Use this to find and return the number of different ways to select the minimum size of match records to remove. However, if 3 or more records must be removed, return 0.

Implementation Details

You must submit a single file named ising.cpp. This file must contain the following function:

long long count_ways( int N, vector<int> U, vector<int> V ) ;

This function must operate as described above. Of course, you can create other functions and use them internally. The submitted code must not perform input/output or access other files.

Grader

The provided grader reads input in the following format:

• line 1: $N$ $M$ ($N$: number of gamers, $M$: number of Icing match records)
• line 2+i ($0 \le i \le M-1$): $U_i$ $V_i$ (Icing match record between gamer $U_i$ and gamer $V_i$)

The provided grader outputs the value returned by your code's count_ways() function.

Constraints

• $3 \le N \le 250,000$
• $N-1 \le M \le 250,000$
• $1 \le U_i, V_i \le N$ ($0 \le i \le M-1$)
• $U_i \neq V_i$
• If $U_i = U_j$ and $V_i = V_j$, then $i = j$ (There is no case where $U_i = V_j$ and $V_i = U_j$)
• Any two gamers are connected through match records (either directly or through the match relationships of other gamers)

Subtasks

• Subtask 1 [10 points]: $N \le 200, M \le 200$
• Subtask 2 [23 points]: $N \le 5,000, M \le 5,000$
• Subtask 3 [11 points]: $N \le 500$
• Subtask 4 [25 points]: $N \le 5,000$
• Subtask 5 [31 points]: $M-N \le 200$
• Subtask 6 [50 points]: No additional constraints.

Examples

Input 1

4 4
1 2
1 3
2 4
3 4

Output 1

1

Note 1

The following shows the function call and its result for Example 1: count_ways( 4, {1, 1, 2, 3}, {2, 3, 4, 4} ) returns 1.

Input 2

4 4
1 2
1 3
1 4
2 3

Output 2

3

Input 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Output 3

3

Input 4

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

Output 4

0

Input 5

12 16
1 2
2 3
3 4
4 1
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 5
1 5
2 7
3 9
4 11

Output 5

2