Icing

Interview

Time limit3sMemory limit1024 MB

Summary

Given battle records as edges, count the smallest sets of at most two edges whose deletion makes the graph bipartite, or return 0 if none exists.

Level: Medium5 of 10
Topics: Graph, BFS, Combinatorics
Solved: No attempts yet

x

Icing is an online one-on-one battle game that is popular among many middle and high school students. The game company expanded it into Icing II, a team-play-only mode in which a team I and a team Sing can battle each other. Icing II is designed to form teams in a unique way based on players' existing battle records in Icing. That is, two players who had a one-on-one battle in Icing must belong to different teams. Each team must have at least one player, and the two teams may have different sizes.

For example, the table below shows how players A, B, C, and D formed Icing II teams using their one-on-one Icing battle records.

However, Icing II launches in three minutes, and a fatal problem was found. For example, if players A, B, and C have all battled each other, they must each go to a different team, so splitting them into team I and team Sing is impossible.

To fix this, the team plans to delete the fewest battle records possible. For example, take the case on the left of the figure below, where players A, B, C, and D have the battle records shown. At least one record must be deleted. If the A-B record is deleted (middle), the two teams can be formed (right).

As another example, consider the following battle records. At least two records must be deleted. If the A-B and C-D records are deleted, the two teams can be formed as shown below.

However, only three minutes remain before launch, so at most two records can be deleted. If three or more records must be deleted, it may be better to postpone the launch.

The company's director wants to know how many different sets of the smallest size of battle records can be deleted to form two teams. That is, when the minimum number of records to delete is $K$ , count the subsets of battle records of size $K$ that can be deleted.

In Example 2, deleting any one of {A-B}, {A-C}, or {B-C} allows two teams to be formed with the minimum number of deletions. The answer for this case is 3. In Example 3, deleting any one of {A-B, C-D}, {A-C, B-D}, or {A-D, B-C} allows two teams to be formed with the minimum number of deletions. The answer for this case is 3.

You must implement the following function to count the number of different ways to choose the minimum number of battle records to delete so that two teams can be formed from the given Icing battle records. The order of the chosen records does not matter. If the game cannot proceed by deleting two or fewer records, return 0. If no records need to be deleted, the only way is to delete nothing, so the count is 1.

long long count_ways( int N, vector<int> U, vector<int> V ) ; N is the number of players. U and V are vectors of size M, and a battle record exists between U[i] and V[i]. Using these, return the number of different ways to choose the minimum-size set of records to delete. If three or more records must be deleted, return 0.

Examples5

Example 1
Input
```
4 4
1 2
1 3
2 4
3 4
```
Expected output
```
1
```
Example 2
Input
```
4 4
1 2
1 3
1 4
2 3
```
Expected output
```
3
```
Example 3
Input
```
4 6
1 2
1 3
1 4
2 3
2 4
3 4
```
Expected output
```
3
```

Example 4

Input

Expected output

Example 5

Input

Expected output