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. friends numbered 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 and are in the same game and on opposite teams |
T a b |
Friends and are in the same game and on the same team |
After being given 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 players on a team and players on the other teams, then the imbalance is .
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 😖
Constraints
Input Specification
The first line contains two integers: and
The next 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
2
Sample Explanation
Firstly, friend and are opponents. Since is an opponent of , they must be in the same team as . There are no further relationships, so we know that and are playing , and that is playing a solo game. The total imbalance is thus
Sample Input
4 3
O 1 2
O 1 3
O 2 3
Sample Output
IMPOSSIBLE
Sample Explanation
There's no way for friends ,, and to be assigned to exactly teams. So, this creates an impossible situation.
Comments