Олонлог Эгзэ сургуулийн хоёр өөр ангийн сурагчид автобусны сүлжээний зураг гаргажээ.

Сүлжээ бүр дараах байдлаар өгөгдөнө:

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

Танд хоёр graph өгөгдөнө.

? Таны зорилго:

Эдгээр хоёр graph ижил бүтэцтэй юу?

? Тайлбар

Хоёр graph-ийг ижил гэж үзэхийн тулд:

• Нэг graph-д байгаа бүх edge нөгөөд нь байх ёстой
• Нөгөөд байгаа бүх edge эхний graph-д байх ёстой

? Өөрөөр хэлбэл edge-үүд яг адил байх ёстой

Оролт:

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

N M1

• N — оройн тоо
• M1 — эхний graph-ийн ирмэгийн тоо

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

u v

• эхний graph-ийн edge

Дараагийн мөрөнд:

M2 — хоёр дахь graph-ийн ирмэгийн тоо

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

u v

• хоёр дахь graph-ийн edge

? Аль аль нь чиглэлгүй (undirected) graph

Гаралт:

• Хэрэв graph-ууд ижил бол: YES
• Үгүй бол: NO

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

• 1 ≤ N ≤ 100000
• 0 ≤ M1, M2 ≤ 100000
• 1 ≤ u, v ≤ N

Дэд бодлого

Жишээ:

Оролт-1

3 2
1 2
2 3
2
2 1
3 2

Гаралт-1

YES

Тайлбар

Edge-үүд ижил (зөвхөн дараалал өөр)

Оролт-2

3 2
1 2
2 3
1
1 2

Гаралт-2

NO

Оролт

4 2
1 2
3 4
2
1 2
2 3

Гаралт

NO