B. Раундын бодлогууд

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

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

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

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

Дараагийн Кодфорсесийн раундад зориулан бэлдсэн $n$ бодлого байна. Тэд шийдэхэд хүндрэлтэй байдлаараа өсөхөөр эрэмбэлэгдсэн ба ямар ч хоёр бодлогыг шийдэх хүндрэл нь ижил байхгүй. Мөн түүнчлэн төсөөтэй бодлогуудын $m$ хос байна. Зохиогчид бодлогуудыг дараах дүрмүүдийн дагуу хоёр хэсэгт хуваахыг хүсч байна:

  • Хэсэг бүрийн бодлогын бүрдэл хоосон биш байх ёстой.
  • Бодлого бүр яг нэг хэсэгт ашиглагдана (тиймээ, энэ жирийн биш шаардлага).
  • 1-р хэсэгт ашиглагдсан бодлого бүр 2-р хэсэгт ашиглагдсан бодлого бүрээс хэцүү байх ёстой.
  • Хэрвээ хоёр бодлого төсөөтэй бол тэд ялгаатай хэсэгт ашиглагдах ёстой.

Таны зорилго бол бүх нөхцөлийг хангахаар бодлогуудыг хоёр хэсэгт хуваах боломжуудыг тоолох юм. Хэрвээ 1-р хэсэг болон 2-р хэсэгт хамааралтай ядаж нэг бодлогоороо ялгаатай бол уг хоёр хуваалт нь ялгаатайд тооцогдоно.

Төсөөтэй гэх хамаарал нь дамжихгүй. Өөрөөр хэлбэл хэрвээ $i$ бодлого нь $j$ бодлоготой төсөөтэй ба $j$ бодлого $k$ бодлоготой төсөөтэй бол $i$ бодлого $k$ бодлоготой төсөөтэй гэсэн үг биш.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($2 ≤ n ≤ 100 000$, $0 ≤ m ≤ 100 000$) байх ба харгалзан раундад зориулан бэлдсэн бодлогуудын тоо болон төсөөтэй бодлогуудын хосын тоо байна.

Дараагийн $m$ мөр бүрт төсөөтэй бодлогын хос $u_{i}$ ба $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}$) байна. Ямар ч хос бодлого оролтонд хоёр байхгүй нь тодорхой.

Гаралт

Бодлогуудыг хоёр хэсэгт хуваах боломжит замуудын тоог илэрхийлэх бүхэл тоон утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
5 2
1 4
5 2
Гаралт
2
Оролт
3 3
1 2
2 3
1 3
Гаралт
0
Оролт
3 2
3 1
3 2
Гаралт
1

Тэмдэглэл

Эхний жишээн дээр $1$ ба $2$ бодлогууд нь 2-р хэсэгт ашиглагдах ёстой бол $4$ ба $5$ бодлогууд 1-р хэсэгт ашиглагдах ёстой. $3$-р бодлого 1 эсвэл 2-р хэсэгт алинд нь ч ашиглагдаж болно.

Хоёр дахь жишээн дээр бодлогуудын бүх хос төсөөтэй ба ямар ч дүрмийг зөрчихгүйгээр бодлогуудыг хоёр хэсэгт хуваах боломж байхгүй.

Гурав дахь жишээ танд төсөөтэй хамаарал дамжихгүй гэдгийг сануулна. $3$-р бодлого $1$ ба $2$ аль алинтай нь төстэй боловч $1$-р бодлого $2$-той төстэй биш, иймд тэд цуг ашиглагдаж болно.

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