In a game of Capture The Flag, exactly two opposing teams will compete against each other to collect the other team's flag! Teams can be empty, and in that case, the team will play against bots. ~N~ friends numbered ~1\dots N~ want to play some number of concurrent games of Capture The Flag. To do so, they enter their names into a computer and the computer randomly assigns relationships:
||Friends ~a~ and ~b~ are in the same game and on opposite teams|
||Friends ~a~ and ~b~ are in the same game and on the same team|
After being given ~M~ such relationships, the friend tried to split themselves into games such that the number of games is maximal (i.e. if they can't be sure if two people are in the same game, they will be regarded as in different games). However, there's a chance that the relationships the computer gave out is invalid, which happens when two people are theoretically in the same team and not in the same team at the same time. Please find out if the computer's output was invalid, and if not, the total imbalance of all of the games.
The imbalance of a game is the absolute difference between the number of players on the two teams. More formally, if there are ~p~ players on a team and ~q~ players on the other teams, then the imbalance is ~|p-q|~.
Do note that it is possible for a friend to have no relationships with anybody else. In this case, he is playing a game by himself :<
Note: Due to incorrect data, AC submissions were given the WA verdict - it has
hopefully been fixed as of December 8, sorry 'bout that 😖
~1\le N\le 2\times 10^5~
~1\le M\le 2\times 10^5~
~1\le a,b\le N~
The first line contains two integers: ~N~ and ~M~
The next ~M~ lines each contain a relationship. The input format is the same as what the table above specifies.
If the relationships form an invalid scenario, output
IMPOSSIBLE. Otherwise, output one integer, the total imbalance of all the games.
4 2 O 1 2 O 2 3
Firstly, friend ~1~ and ~2~ are opponents. Since ~3~ is an opponent of ~2~, they must be in the same team as ~1~. There are no further relationships, so we know that ~1~ and ~3~ are playing ~2~, and that ~4~ is playing a solo game. The total imbalance is thus ~|2-1|+|1-0|=2~
4 3 O 1 2 O 1 3 O 2 3
There's no way for friends ~1~,~2~, and ~3~ to be assigned to exactly ~2~ teams. So, this creates an impossible situation.