配点:700700

問題文

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

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

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

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

制約

  • 2N2×1052 \leq N \leq 2\times 10^5
  • N/2MNN/2 \leq M \leq N
  • 1Ai,BiN1 \leq A_i,B_i \leq N (1iM)(1\leq i\leq M)
  • AiBiA_i\neq B_i (1iM)(1\leq i\leq M)
  • iji\neq j ならば AiAjA_i\neq A_j (1i,jM)(1\leq i,j\leq M)
  • iji\neq j ならば BiBjB_i\neq B_j (1i,jM)(1\leq i,j\leq M)
  • 任意の ll (1lN)(1\leq l\leq N) に対して As=lA_s=l もしくは Bs=lB_s=l を満たす ss が存在する
  • 入力は全て整数である

入力

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

NN MM

A1A_1 B1B_1

A2A_2 B2B_2

...

AMA_M BMB_M

出力

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

サンプル

入力1
3 2
1 2
2 3
出力1
1 7

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

22 を向こう岸に渡す(1133 は一緒に残しても大丈夫です)

② riano君だけで戻ってくる

33 を向こう岸に渡す(向こう岸に 22 がいますが、riano君が離れなければ大丈夫です)

22 を連れて戻ってくる

22 を元の岸に残し、11 を向こう岸に渡す(向こう岸に 1133 がいる状態になります)

⑥ riano君だけで戻ってくる

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

入力2
5 4
1 2
3 4
4 5
5 3
出力2
3 3

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

Submit


Go (1.21)