Capture the Flag

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 128M

Problem type

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:

Command Description
O a b Friends a and b are in the same game and on opposite teams
T a b 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

a\ne b

Input Specification

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.

Output Specification

If the relationships form an invalid scenario, output IMPOSSIBLE. Otherwise, output one integer, the total imbalance of all the games.

Sample Input

4 2
O 1 2
O 2 3

Sample Output


Sample Explanation

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

Sample Input

4 3
O 1 2
O 1 3
O 2 3

Sample Output


Sample Explanation

There's no way for friends 1,2, and 3 to be assigned to exactly 2 teams. So, this creates an impossible situation.


There are no comments at the moment.