MST Ирмэгийн Олонлог Шалгалт

2s

512MB

2122

0%

Advanced Graph Problems

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

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

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

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

Дараагийн $m$ мөрөнд ирмэгүүд. Мөр бүр $a$ , $b$ , $w$ гэсэн гурван бүхэл тоог агуулна: $a$ болон $b$ оройнуудын хооронд $w$ жинтэй ирмэг бий. Ирмэгүүд оролтын дарааллаар $1,2,\dots,m$ гэж дугаарлагдсан.

Дараагийн $2q$ мөрөнд ирмэгийн олонлогууд. Олонлог бүрийн хувьд эхний мөрөнд хэмжээ нь, хоёр дахь мөрөнд ирмэгүүд нь байна. Бүх олонлогийн ирмэгийн нийт тоо $m$ -ээс ихгүй.

Граф холбогдсон, энгийн бөгөөд ирмэг бүр графад хамгийн ихдээ нэг удаа орно гэж үзэж болно.

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

Олонлог бүрийн хувьд ирмэгүүдийг хамгийн бага тархалтын модонд оролцуулж болбол YES, үгүй бол NO гэж хэвлэ.

Хязгаарлалт

$1 \le n \le 10^5$
$1 \le m, q \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le w \le 10^9$

Жишээ

Оролт1

Гаралт1

YES
NO
YES
NO

0.1 / 64 KiB

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