A. Граф ба тэмдэгт мөр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэг өдөр оюутан Вася лекцэн дээр сууж байгаад ширээн дээр нь бичсэн байсан "$a$", "$b$" болон "$c$" үсэгнүүдээс бүрдсэн $s_{1}s_{2}... s_{n}$ тэмдэгт мөрийг анзаарсан. Лекц уйтгартай байсан учир Вася зургийг дараах шинж чанартай $G$ графыг зурж гүйцээхээр шийдсэн:

  • $G$ нь яг $n$ оройтой ба $1$-с $n$ хүртэл дугаарлагдсан.
  • Бүх $i ≠ j$ байх $i$ ба $j$ оройнуудын хувьд $s_{i}$ ба $s_{j}$ тэмдэгтүүд нь цагаан толгойн дарааллаар тэнцүү эсвэл хөрш байвал тэднийг холбож байгаа ирмэг байна гэсэн үг. Энэ нь "$a$"-"$c$" тэмдэгтүүд хөрш биш ба "$a$"-"$b$" ба "$b$"-"$c$" тэмдэгтийн хослолууд нь хөрш гэсэн үг

Вася үүсч буй графийг тэмдэгт мөрийн ойролцоо зураад тэмдэгт мөрийг арилгасан. Маргааш нь Васягийн найз Петя лекцэнд ирсэн ба ширээн дээрээсээ уг графийг олсон. Тэр Васягийн энэ адал явдалыг сонссон ба энэ граф анхны Васягийн зурсан $G$ граф мөн эсэхийг мэдэхийг хүсч байна. Үүнийг шалгахын тулд Петя энд өгөгдсөн $G$ графыг гаргаж авахад Васягийн ашигласан $s$ шиг $s$ тэмдэгт мөр байгаа эсэхийг мэдэх хэрэгтэй.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ байх ба харгалзан Петягийн олсон графын орой болон ирмэгийн тоо юм.

Дараагийн $m$ ширхэг мөрийн мөр бүрт хоёр бүхэл тоон утга $u_{i}$ ба $v_{i}$ $(1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i})$ байх ба $G$ графын ирмэгүүд юм. Энэ нь давхар ирмэг байхгүй гэсэн үг буюу жагсаалтад ямар ч хос оройнууд нэгээс илүү харагдахгүй гэсэн үг.

Гаралт

Эхний мөрөнд Петягийн хайж буй тэмдэгт мөр байвал "$Yes$" (хашилтгүйгээр) гэж хэвлэх ба бусад тохиолдолд "$No$" (хашилтгүйгээр) гэж хэвлэнэ.

Хэрвээ $s$ тэмдэгт мөр оршин байвал үүнийг хоёр дахь мөрөнд хэвлэнэ. $s$ тэмдэгт мөрийн урт яг $n$ байх ёстой ба зөвхөн "$a$", "$b$" болон "$c$" үсэгнүүдээс л бүрдэх ба уг тэмдэгт мөрийг ашиглан үүсгэсэн граф $G$ графтай давхцаж байх ёстой. Хэрвээ хэд хэдэн боломжит хариулт байвал та алийг нь ч хэвлэж болно.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
2 1
1 2
Гаралт
Yes
aa
Оролт
4 3
1 2
1 3
1 4
Гаралт
No

Тэмдэглэл

Эхний жишээн дээр танд хоорондоо ирмэгтэй хоёр оройгоос бүрдэх граф өгөгдсөн. Ингээд эдгээр оройнууд нь ижил болон хөрш үсэгнүүдтэй аль алинтай нь харгалзаж чадна. Дараах бүх тэмдэгт мөрүүд графийн нөхцөлтэй тохирно $"aa"$, $"ab"$, $"ba"$, $"bb"$, $"bc"$, $"cb"$, $"cc"$.

Хоёр дахь жишээн дээр эхний орой бусад бүх гурван оройтой холбогдсон боловч тэр гурван орой өөр хоорондоо холбогдоогүй байна. Энэ нь эдгээр гурван орой хөрш биш ялгаатай үсгүүдэд харгалзана гэсэн үг. Гэвч ийм хоёрхон үсэг байгаа нь a, c учир боломжгүй.

Сэтгэгдлүүдийг ачааллаж байна...