Сургуулийн бүжиг

2s

512MB

1491

0%

Graph Algorithms

Сургуульд $n$ хөвгүүд, $m$ охид байна. Дараагийн долоо хоногт сургуулийн бүжиг зохион байгуулна. Бүжгийн хос нэг хөвгүүн болон нэг охиноос бүрдэнэ, $k$ боломжит хос байна.

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

https://cses.fi/problemset/task/1696

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

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

Үүний дараа боломжит хосуудыг тодорхойлсон $k$ мөр байна. Мөр бүрд хоёр бүхэл тоо $a$ ба $b$ : хөвгүүн $a$ ба охин $b$ хамт бүжиглэхийг хүснэ.

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

Эхлээд нэг бүхэл тоо $r$ хэвлэ: бүжгийн хосуудын хамгийн их тоо. Үүний дараа хосуудыг тодорхойлсон $r$ мөр хэвлэ. Ямар ч зөв шийдийг хэвлэж болно.

Хязгаарлалт

$1 \le n,m \le 500$
$1 \le k \le 1000$
$1 \le a \le n$
$1 \le b \le m$

Жишээ

Оролт1

Гаралт1

2
1 2
3 1

0.1 / 64 KiB

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