M. Who Is a Titan?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In Attack on Titan, Titans are a constant threat to humanity. These giant humanoid creatures can cause significant destruction and loss of life, and identifying them is crucial to protect civilians and defend against them.

In this fictional world, there are two primary nations, Marley and Paradis, and a number of small unnamed nations.

A long, long time ago, there were $$$N$$$ humans with the power of the Titans (initially all from different, small unnamed nations). As history progressed, smaller nations inevitably merged into the larger two nations, and many titan-transformers from the smaller nations were forced to join either Marley or Paradis.

As a historian, you are trying to recover some information about the battles between the nations, and the ultimate fates of each titan-transformer. You've collected a list of $$$Q$$$ historical records and sorted them in decreasing order of credibility. Each of the $$$Q$$$ statements describe a battle between Marley and Paradis and takes one of two forms:

  • 0 a b: Titans $$$a$$$ and $$$b$$$ fought together and then both joined the same nation (either both joined Paradis or both joined Marley; the record doesn't specify which).
  • 1 a b Titans a and b fought against each other and then both joined different nations (either Titan a joined Paradis and b joined Marley, or vice-versa).

Process each historical record in order. For each record $$$q_i$$$, if the information in that record contradicts facts derivable from previous records, print IMPOSSIBLE. Record $$$q_i$$$ is then discredited as potentially fake and you should ignore its information when considering all future records.

If $$$q_i$$$ does not contradict previous records, print the maximum number of titan-transformers that a single nation could have, based on the records you've processed so far. Also print the maximum number of different nations (including Marley and Paradis) that could harbor at least one of the $$$N$$$ Titans based on the records so far.

Important: a historical record might specify a battle involving the same Titan twice, where $$$a=b$$$. A record of the form 1 a a that specifies a Titan joined a different nation than themselves is a self-contradiction and automatically discredited.

Input

The first line contains two space-separated integers $$$N$$$ and $$$Q$$$ $$$(1\leq N, Q\leq 10^5).$$$ Each of the next $$$Q$$$ lines contains information about one historical battle. The $$$i$$$th such line contains three space-separated integers $$$t_i$$$, $$$a_i$$$, and $$$b_i$$$ describing the historical record $$$q_i$$$: the type of record $$$t_i\in\{0,1\}$$$, and the two Titans involved in the battle $$$1 \leq a_i, b_i \leq N$$$. It is possible that $$$a_i = b_i$$$.

Output

For each record $$$q_i$$$, print one line of output. If $$$q_i$$$ contradicts facts derivable from earlier (non-discredited) records or is a self-contradiction, print $$$\texttt{IMPOSSIBLE}$$$. Otherwise, print two integers: the maximum possible number of Titans that a single nation could have based on records so far, and the maximum number of nations that could have at least one Titan based on the records so far.

Examples
Input
4 4
0 1 2
1 2 3
1 1 2
0 3 4
Output
2 3
2 3
IMPOSSIBLE
2 2
Input
4 3
1 1 2
1 2 3
1 3 1
Output
1 4
2 3
IMPOSSIBLE