配点：$700$ 点

問題文

riano君は $N$ 匹の動物（ $1,2,...,N$ と順に番号がついています）を連れて旅をしており、大きな川にさしかかりました。 この川を渡るには渡し舟を使うしかありませんが、舟にはriano君のほかに動物 $K$ 匹までしか一度に乗れません。

厄介なことに、riano君の連れている動物たちの何組かは、好物と天敵の関係にあります。 動物 $A$ が動物 $B$ の天敵であるというとき、 この $2$ 匹が川の同じ側の岸にいて、riano君がその場にいない場合、$A$ が $B$ を食べてしまうということを意味します。 同じことを、動物 $B$ が動物 $A$ の好物である、とも表現することにします。 なお、$A$ と $B$ が互いを好物と考えている場合も含めて、複数の「好物と天敵の関係」が存在する場合には、ランダムに食べられる順が決められ、そのような関係がなくなるまで残った動物のみが生き残ります。

riano君の連れている動物たちの中には全部で $M$ 個の関係があり、 $A_i$ が $B_i$ の天敵である（すなわち、 $B_i$ が $A_i$ の好物である）ことが分かっています $(1\leq i\leq M)$ 。 ただし、各動物について、天敵と好物はそれぞれ高々 $1$ 匹ずつしかいないこと、 および天敵も好物もいない動物は存在しないことが保証されます。 また、riano君が舟に乗らず、動物だけを乗せて川を渡らせることはできません。

riano君は、全ての動物が無事なまま、自身と全ての動物を川の向こう岸に渡したいと考えています。 これが可能であるような最小の $K$ を求めてください。 また、そのような渡し舟がある場合、riano君は最小で何度、舟で川を横切る必要があるでしょうか。

制約

• $2 \leq N \leq 2\times 10^5$
• $N/2 \leq M \leq N$
• $1 \leq A_i,B_i \leq N$ $(1\leq i\leq M)$
• $A_i\neq B_i$ $(1\leq i\leq M)$
• $i\neq j$ ならば $A_i\neq A_j$ $(1\leq i,j\leq M)$
• $i\neq j$ ならば $B_i\neq B_j$ $(1\leq i,j\leq M)$
• 任意の $l$ $(1\leq l\leq N)$ に対して $A_s=l$ もしくは $B_s=l$ を満たす $s$ が存在する
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられます。

出力

はじめに題意の $K$ の最小値を出力し、空白区切りで、そのような $K$ に対してriano君が舟で川を横切る回数の最小値を出力してください。

サンプル

3 2
1 2
2 3

1 7

動物 $1$ と $2$ 、$2$ と $3$ はそれぞれ同時に岸に残すことができません。 このとき、 $K=1$ で次のような手順が可能であり、これが最適です。

① $2$ を向こう岸に渡す（$1$ と $3$ は一緒に残しても大丈夫です）

② riano君だけで戻ってくる

③ $3$ を向こう岸に渡す（向こう岸に $2$ がいますが、riano君が離れなければ大丈夫です）

④ $2$ を連れて戻ってくる

⑤ $2$ を元の岸に残し、$1$ を向こう岸に渡す（向こう岸に $1$ と $3$ がいる状態になります）

⑥ riano君だけで戻ってくる

⑦ $2$ を向こう岸に渡し、全ての動物とともに川を渡ることができました

5 4
1 2
3 4
4 5
5 3

3 3

動物 $3$、$4$、$5$ はいわゆる三すくみの天敵関係を持っていますが、これらを岸に残した場合もランダムにいずれかの動物が食べられてしまうことに注意してください。