s02198. 农夫渡河 未做

农夫要带 $n$ 样物品过河，船很小：每次只能载农夫和至多两样物品，且农夫必须划船。此外还给了若干条「不能共处」的约束：每条约束形如 $(u,v)$，表示在没有农夫看管的岸上，物品 $u$ 与物品 $v$ 不能同时停留。求把农夫与全部物品都送到对岸所需的最少渡河次数；若无法完成输出 $-1$。

第一行两个整数 $n,m$。接下来 $m$ 行，每行两个整数 $u,v$（$1\le u<v\le n$），表示 $u$ 与 $v$ 不能在没有农夫的岸上共处。

一行一个整数，最少渡河次数；无法完成输出 -1。

• 对于 30% 的数据：$n\le 3$
• 对于 60% 的数据：$n\le 4$
• 对于 100% 的数据：$n\le 5$，$0\le m\le \frac{n(n-1)}{2}$，$1\le u<v\le n$