Need help in an 1700ish graph problem

Revision en2, by bgopc, 2024-02-20 19:58:39

In a weird high school, there are $n$ students, and the school principal Mr. X wants to make students happy so he decides to throw a couples' party.
In this high school, between every 2 person, there can be 4 types of relationships:
1: they love each other
2: The first loves the second but the second doesn't
3: The second loves the first but the first doesn't
4: they don't like each other

At this party, people will be grouped into Pairs of couples.
The relationship between them determines the happiness of a pair:
type 1: happiness 2, type 2,3: happiness 1, type 4: happiness -1
if a person gets left out(I.E n is odd) there will be a -2 happiness for him

Since Mr. X is a happy person he wants to maximize the sum happiness of the party. Since he is a busy person He asks you to do that

Input Format
In The First Line, there will be one integer $n$: $n$, ($1 \leq n \leq 10^5$) the number of people at the party. In the Second line will be $m$, the number of people who love a person ($1 \leq r \leq 10^5$)
In the following $m$ lines there will be a format: two indexes $i$, $j$ meaning the person $i$ loves the person $j$. (Two-sided love will be given in 2 separate lines, if there isn't a directed edge between 2 people their relationship is type 4)

Output Format In the only line of the output, print the maximum happiness of the party

So today I came up with this problem and actually got stuck in solving it. Appreciate any helps

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 bgopc 2024-02-20 19:58:39 80
en1 bgopc 2024-02-20 19:54:40 1461 Initial revision (published)