D. Жорж ба сонирхолтой граф

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жорж бол графт дуртай нэгэн юм. Тэрээр үргэлж сонирхолтой графт дуртай байдаг. Бид хэрэв чиглэлтэй граф нь дараах нөхцөлүүдийг хангаж байвал уг графыг сонирхолтой граф гэж үзнэ:

  • Граф нь ямар ч олон тооны нумууд агуулаагүй байна;
  • Графын ямар ч $u$ оройн хувьд уг граф нь $(u, v)$ болон $(v, u)$ нумуудыг агуулж байхаар $v$ орой оршин байна (бид үүнийг төв гэж нэрлэнэ). Уг граф нь $(v, v)$ гогцоог мөн агуулж байхыг анхаарна уу.
  • Төвөөс бусад бүх оройнуудын гадаад өнцөг нь 2-той тэнцүү байх ба дотоод өнцөг нь мөн 2-той тэнцүү байна. $u$ оройн гадаад өнцөг гэдэг нь $u$ оройгоос гарч буй нумуудын тоог хэлнэ. $u$ оройн дотоод өнцөг гэдэг нь $u$ орой уруу орж буй нумуудын тоог хэлнэ. Уг граф нь гогцоо агуулж болохыг анхаарна уу.

Тэгсэн хэдий ч бүх зүйл тийм хялбар байсангүй. Жорж бэлэг болгон $n$ орой болон $m$ нум бүхий чиглэлтэй граф авчээ. Уг граф нь ямар ч олон тооны нумууд агуулаагүй байв. Жорж сонирхолтой графт дуртай учраас тэрээр бэлгийн графыг үл ялиг өөрчлөн сонирхолтой граф болгон хувиргахыг хүсжээ. Нэг өөрчлөлтөөр тэрээр уг графын оршин байгаа дурын нэг нумыг авч хаяна эсвэл дурын нэг нумыг уг графт нэмэх юм.

Одоо Жорж өөрийн бэлгийн графаас сонирхолтой граф гаргаж авахын тулд хийх ёстой хамгийн цөөн өөрчлөлтийн тоог мэдэхийг хүсжээ. Түүнд туслан асуултын хариултыг олж өгнө үү.

Оролт

Эхний мөрөнд графын оройнууд болон бэлгийн граф дахь нумуудын тоог илэрхийлэх зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ болон $m$ ($2 ≤ n ≤ 500, 1 ≤ m ≤ 1000$) өгөгдөнө.

Дараагийн $m$ мөрийн мөр болгонд зайгаар тусгаарлагдсан 2 бүхэл тоо $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$) өгөгдөх ба эдгээр нь уг графын нумуудын тайлбар болно. $(a_{i}, b_{i})$ хос нь уг граф нь$a_{i}$ дугаартай оройгоос $b_{i}$ дугаартай орой хүртэл нэг нум агуулж байгааг илэрхийлнэ. Уг граф нь ямар ч олон тооны нум агуулаагүй байх юм.

Графын оройнууд нь 1-ээс $n$ хүртэл дугаарлагдсан гэж үзнэ үү.

Гаралт

Жорж-ын асуултын хариулт болох ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 7
1 1
2 2
3 1
1 3
3 2
2 3
3 3
Гаралт
0
Оролт
3 6
1 1
2 2
3 1
3 2
2 3
3 3
Гаралт
1
Оролт
3 1
2 2
Гаралт
6

Тэмдэглэл

Чиглэлтэй графын талаарх илүү их мэдээллийг доорх хаягаар орж харна уу:

http://en.wikipedia.org/wiki/Directed_graph

Эхний жишээнд граф нь аль хэдийн сонирхолтой байх ба үүний төв нь $3$ дугаартай орой байна.

Сэтгэгдлүүдийг ачааллаж байна...