Maximum Team Matching

You are given n employees and m potential pairs of employees who can work together for a team‐building activity. In this activity, employees are paired up in one-on-one teams, and an employee can participate in at most one pair.

Your task is to determine the maximum number of employees that can participate by forming the maximum number of disjoint pairs. Note that if an edge (pair) appears more than once, it should be treated as a single possible pairing. The answer is twice the number of pairs in the maximum matching.

Note: It is guaranteed that the graph formed by the employees and pairs is bipartite. You can use a bipartite matching algorithm (e.g. Hopcroft–Karp) to solve this problem.

The relation between the maximum matching and the answer is given by:

\(\text{Answer} = 2 \times \text{(number of pairs in the maximum matching)}\).

inputFormat

The input is given from standard input and consists of multiple lines. The first line contains two integers n and m where (1 \leq n \leq 10^5) (the number of employees) and (0 \leq m \leq 10^5) (the number of available pairs). Each of the following m lines contains two integers u and v ((1 \leq u, v \leq n)), meaning that employee u can pair with employee v for the activity. Duplicate pairs may appear in the input.

outputFormat

Output to standard output a single integer indicating the maximum number of employees that can participate in the team‐building activity (i.e. twice the number of pairs in the maximum matching).## sample

5 4
1 2
1 3
2 4
3 4

4