Хотын автобусны буудлууд хоорондоо зарим нь шууд замаар холбогдсон байдаг.

Бид буудлуудыг дараах байдлаар загварчилна:

• Буудал бүр → нэг орой (node)
• Шууд зам → ирмэг (edge)

Танд хотын автобусны сүлжээ өгөгдөнө.

Дараа нь Q ширхэг асуулт ирнэ. Асуулт бүр:

? u ба v буудлын хооронд шууд зам байна уу?

гэдгийг асууна.

? Зорилго

Асуулт бүрт:

• Хэрэв u ба v хооронд шууд зам байвал → YES
• Үгүй бол → NO

гэж хариул.

Оролт:

Эхний мөрөнд гурван бүхэл тоо өгөгдөнө:

N M Q

• N — буудлын тоо
• M — замын тоо
• Q — асуултын тоо

Дараагийн M мөр бүрт:

u v

• u болон v буудлын хооронд шууд зам байна

Дараагийн Q мөр бүрт:

u v

• шалгах буудлууд

? Энэ нь чиглэлгүй (undirected) граф

Гаралт:

Асуулт бүрт нэг мөрөнд:YES эсвэл NO гэж хэвлэнэ.

Хязгаарлалтууд:

• 1 ≤ N ≤ 100000
• 0 ≤ M ≤ 100000
• 1 ≤ Q ≤ 100000
• 1 ≤ u, v ≤ N

Дэд бодлого

Жишээ:

Оролт-1

4 3 3
1 2
2 3
3 4
1 2
1 3
2 4

Гаралт-1

YES
NO
NO

Тайлбар

• 1 ↔ 2 → YES
• 1 ↔ 3 → шууд биш → NO
• 2 ↔ 4 → шууд биш → NO

Оролт-2

3 1 2
1 2
1 2
2 3

Гаралт-2

YES
NO