Эйлерийн Дэд Графууд

2s

512MB

1738

0%

Advanced Techniques

$n$ орой, $m$ ирмэгтэй чиглэлгүй граф өгөгдөв.

Анхны графын бүх орой болон зарим ирмэгтэй дэд графуудыг авч үзнэ. Орой бүрийн зэрэг тэгш бол дэд графыг Эйлерийн гэнэ.

Эйлерийн дэд графуудын тоог $10^9+7$ -ийн модулаар тоол.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$ : орой ба ирмэгийн тоо. Оройнууд $1,2,\dots,n$ гэж дугаарлагдана.

Дараа нь ирмэгүүдийг тодорхойлсон $m$ мөр байна. Мөр бүрт хоёр бүхэл тоо $a$ ба $b$ : $a$ , $b$ оройнуудын хооронд ирмэг байна. Хоёр оройн хооронд хамгийн их нэг ирмэг байх бөгөөд ирмэг бүр хоорондоо ялгаатай хоёр оройг холбоно.

Гаралтын формат

Эйлерийн дэд графуудын тоог $10^9+7$ -ийн модулаар хэвлэ.

Хязгаарлалт

$1 \le n \le 10^5$
$0 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...