E. Сонирхолтой граф ба алимнууд

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

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

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

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

Hexadecimal зурах дуртай. Тэр чиглэлтэй, чиглэлгүй олон граф зурж байсан. Сүүлийн үед тэрээр бүх орой нь ганцхан цагирагт багтдаг графыг их сонирхож байгаа. Тэр үүнийг зугаатай цагираг гэж нэрлэдэг. Зангилаа нь бас зугаатай цагираг юм(Өөрөө өөртэйгээ холбогдсон орой).

Тэрээр зугаатай цагираг зурахын өмнө хэдэн ирмэгийг зурсан байсан ба үлдсэн зарим нэг оройнуудыг холбон зугаатай цагираг үүсгэхийг хүсч байв. Зугаатай цагираг үүсгэх ирмэгүүдийн хамгийн багадаа хэдэн ширхэг хэрэгтэй вэ? Цагаан толгой дарааллаар хамгийн эхэнд орших зугаатай цагираг үүсгэх хариуг хэвлэ. Бодлогын ямар нэг хариу болох ирмэгийн олонлогыг хосоор нь дараалуулан бичвэл ($u_1$,$v_1$),($u_2$,$v_2$),...,($u_n$,$v_n$) дээрх дараалал нөхцлийг хангана $u_i$≤$v_i$($u_i$ болон $v_i$-н хооронд ирмэг байгааг илэрхийлнэ).

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n$,$m$ ($1 ≤ n ≤ 50$, $0 ≤ m ≤ 2500$)- оройн тоо болон зурагдсан ирмэг. Дараагийн $m$ мөрөнд зурагдсан байсан ирмэгийг илэрхийлэх $x_i$, $y_i$ ($1 ≤ xi, yi ≤ n$).

Гаралт

Эхний мөрөнд "YES", "NO" хоёрын аль нэг нь байна. Хэрвээ "YES" байвал зугаатай цагираг үүсгэх боломжтой бөгөөд хоёрт дахь мөрөнд $k$- хэдэн ирмэг нэмэх шаардлагатай илэрхийлэх тоог хэвлнэ. Дараагын $k$ мөрөнд $u_i$, $v_i$ хосуудыг хэвлэнэ.

Орчуулсан: byambadorjp

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

Оролт
3 2
1 2
2 3
Гаралт
YES
1
1 3
Сэтгэгдлүүдийг ачааллаж байна...