動物間に好物と天敵の関係がある時、いずれであっても同じ岸に残しておけない、という条件となりますので、無向グラフとみなしてよいです。 制約より、各頂点（動物）の次数は または であることが分かります。 すなわち、
- 孤立点がない
- 各連結成分はパスまたはループである
ことが分かります。まずは連結成分ごとに考えましょう。
パスについて、サイズを とすると、明らかに 匹（以下、この表記において、商の整数部分を表すこととします。）を最初に舟に乗せていく必要があります。 隣接する頂点を残すことはできませんので、二部グラフとみなしたときのサイズの小さい方に属する頂点を取り除く必要があるからです。 偶数長のパスに対しては、これは明らかに十分であり、riano君は 回に分けて全動物を運びきることが可能です （この時川を渡る回数は 回です）。 奇数の場合も実は、サンプルで与えられているように、これを舟の定員とすれば十分で、サンプルと同様にパスの端から入れ替えていくような方法で 回で渡り切ることを達成できます。 この際、最後に川を渡っているとき、ちょうど最初の状態と対称になっている必要があることに注意してください。 すなわち、最初岸に残した動物たち（二部グラフの大きい方の頂点群）は向こう岸に待機している状態である必要があります （この先の考察の鍵になります）。
ループについて、サイズを とすると、偶数長の場合はパスと全く同じです。 奇数長のループについては、最初に 匹を舟に乗せていく必要があります。 これは、適当な頂点を一つ選んでそれを取り除くと偶数長のパスで二部グラフとなり、 最初に取り除いた頂点に加えてこの中の半分を取り除く必要があるからです。 この場合も舟に乗る回数は 回で済みますが、向こう岸には 匹しか置いてこれない、 すなわち 匹は常に舟に乗せている必要があることに注意してください （最初に取り除いた頂点は、二部グラフのどちらの成分とも共存できないためです）。
以上から、パスおよびループについて、それぞれ必要な舟の容量が分かりました。 また、奇数長のパス以外は 回、奇数長のパスは 回で渡り切れることも分かりました。 続いて、連結成分が複数ある場合を考えます。 舟の容量については、各連結成分の要求する容量の和が必要かつ十分です。 また、舟に乗る回数について、以下のことが自明に分かります。
- 連結成分に奇数長のパスが含まれない場合、 回が最適である
- 奇数長のパスが含まれる場合、多くとも 回以内で渡りきることができる
したがって、残る問題は「奇数長のパスが含まれるときに 回未満で渡ることができる場合があるか、 またそれが可能になるのはどのような場合か」ということになります。
ここで、渡りきる直前には、奇数長のパスについて、 二部グラフの大きい方の成分にあたる動物が全て向こう岸にいなければいけないという事実を用います。 これは、舟の容量の決め方が、全体から「岸に共存できる動物の最大の集合」を除いて決めているため、 向こう岸には「岸に共存できる動物の最大の集合」が存在していなければならないからです。
この条件より、奇数長のパスがある場合に 回で渡りきることは不可能です。 また、 回で渡りきるためには、 往復した直後の時点において、上記を実現しなければいけません。 これを実現するためには、 回目（ 往復目の往路）に各奇数長のパスごとに 匹を乗せて向こう岸に渡り、 回目（ 往復目の復路）に向こう岸にいた 匹を連れて戻ってくることができればよいです。 ただし、奇数長のループが存在する場合、各 匹ずつを常に舟に乗せている必要があり、 この分だけ舟の容量が圧迫されていることに注意してください。
以上をまとめると、答えは下記のようになります。なお、各連結成分のサイズを とします。
舟の容量 について、以下の総和が答えです。
- 奇数長のパスについて
- 奇数長のループについて
- 偶数長のパス、ループについて
回数について、コスト を以下の総和と定義します。
- 奇数長のパスについて
- 奇数長のループについて
- 偶数長のパス、ループについて
このとき、最適な回数は以下の通りです。
- 奇数長のパスが無ければ 回
- 奇数長のパスがあり、 であれば 回
- それ以外の場合 回
なお、強い制約によりグラフの形状は限定されているため、実装上はunionfindなどを用いて、 連結成分の大きさと、ループが生じたかの判定のみを管理すれば十分です。