"Олонлог Эгзэ" сургуулийн сурагчид шинэ жилийн баяраар "монита" нэртэй нэгнийгээ нууцаар баярлуулах сонирхолтой үйл ажиллагаа зохион байгуулж байна.

Энэ үйл ажиллагааны дагуу:

• Сурагч бүр өөр нэг сурагчийг нууцаар баярлуулна
• Гэхдээ бэлгийг шууд өгөхгүй, заавал өөр нэг найзаараа дамжуулж өгнө

Өөрөөр хэлбэл:

• Хэрэв A сурагч B сурагчид бэлэг өгөх бол
• A → X → B гэсэн хэлбэртэй, яг нэг завсрын сурагч X байх ёстой
• A сурагч X сурагчтай найз байх
• X сурагч нь B сурагчтай найз байх

Танд сурагчдын хоорондын найзын холбоос өгөгдөнө.

Таны даалгавар бол:

? A сурагч B сурагчид бэлэг өгөхдөө яг нэг найзаараа дамжуулан бэлэг өгөх боломжтой хэдэн найз өөрт нь байгааг мэдэх хэрэгтэй болсон.

Оролт:

• Эхний мөрөнд хоёр бүхэл тоо өгөгдөнө:

  • N - сурагчдын тоо
  • M - найзын холбоосын тоо

• Дараагийн M мөр бүрт хоёр бүхэл тоо өгөгдөнө:

  • u v — u болон v сурагчид найзууд гэдгийг илэрхийлнэ
• Дараагийн мөрөнд Q асуулгын тоо
• Дараагийн Q ш мөрөнд хоёр бүхэл тоо өгөгдөнө:
  • A B — шалгах хоёр сурагч нэгэндээ бэлэг дамжуулж чадах эсэхийг асуусан

Гаралт:

Q ш мөр байх ба тус бүр нь асуулгын дагуу A → X → B (яг 1 завсрын сурагчтай) олдож байвал: YES үгүй бол NO гэж хэвлэнэ

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

• 1 ≤ N ≤ 2000
• 0 ≤ M ≤ 20000
• 1 ≤ Q ≤ 20000
• 1 ≤ u, v ≤ N
• 1 ≤ A, B ≤ N
• Граф нь чиглэлгүй (undirected)

Дэд бодлого

Жишээ:

Оролт-1

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

Гаралт-1

1
0
1

Оролт-2

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

Гаралт-2

1
1