Хориглосон Хотууд

2s

512MB

2278

0%

Advanced Graph Problems

$n$ хот, тэдгээрийн хооронд $m$ зам бий. Каалеппи одоо $a$ хотод бөгөөд $b$ хот руу явахыг хүсэж байна.

Гэвч асуудал бий: Каалеппи саяхан $c$ хотод банк дээрэмдсэн тул уг хотод орж болохгүй — орон нутгийн цагдаа түүнийг барих болно. $c$ хотоор дайралгүйгээр $a$ хотоос $b$ хот руу зам байгаа эсэхийг тогтоо.

Нэмэлт бэрхшээл: $a$ , $b$ , $c$ утгууд өөрчлөгддөг $q$ хүсэлтийг боловсруулах ёстой.

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

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

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

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

Эцэст нь хүсэлтүүдийг илэрхийлсэн $q$ мөр байна. Мөр бүрт $a$ , $b$ , $c$ гурван бүхэл тоо байна: $c$ хотоор дайралгүйгээр $a$ хотоос $b$ хот руу зам байгаа юу?

Аль ч хоёр хотын хооронд зам байдаг гэж үзэж болно.

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

Хүсэлт бүрт ийм зам байвал "YES", үгүй бол "NO" хэвлэ.

Хязгаарлалт

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

Жишээ

Оролт1

Гаралт1

YES
NO
YES

0.1 / 64 KiB

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