003 - 正統主義

40分クオリティーの問題です。
ガバがあっても許してください。

問題

あなたには今から学ぶべきN個の事柄がある。
それを学んでいこうと思う。
しかしあなたは学び方をいくつか持っている。
$A$ $B$と入力された時はA番目の事柄とB番目の事柄を同じ学び方をして学んだことを示す。
ただし$A$, $B$がどちらかが0であった時、もう片方は歴史に学んだことを示し、N+1であった場合は経験に学んだことを示す。
$A$ $B$がM回入力されるが、 経験に学んだ事柄の個数が歴史に学んだ事柄の個数を超えてしまうとまずいのでそのようなときはその入力を無視せよ。
また、歴史に学んだ事柄と経験に学んだ事柄を同じ学び方をするとなるような入力があると矛盾が起きてしまうのでそれも無視せよ。
その操作の後、歴史に学んだ事柄の個数と経験に学んだ事柄の個数を出力せよ。
なお、歴史あるいは経験に学んだかどうか判明していないものと判明しているものが同じ学び方をしたならば、判明していなかったものの学び方が歴史あるいは経験で学んだのであることを意味する。

入力

N M
A1 B1
......
AM BM

出力

sizeOf_REKISI_
sizeOf_KEIKEN_

歴史に学んだ個数と経験に学んだ個数を改行区切りで出力する。

制約

$1$ ≤ $N$ ≤ $10$⁶
$1$ ≤ $M$ ≤ $10$⁶
$0$ ≤ $A$, $B$ ≤ $N+1$

テストケース

例1

入力

1 1
1 2

1番目を経験に学ぼうとしたが、歴史に学んだ個数より多くなるため無視する。

出力

0
0

例2

入力

5 3
1 0
5 6
1 2

まず1番目を歴史に学んだ。 その後5番目を経験に学んだ。 最後に2番目も歴史に学んだ。

出力

2
1