C. Граф хайж байна

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

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

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

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

Дараах нөхцлүүдийг хангах $n$ оройтой чиглэлгүй графыг $p$-онцлогтой гэж нэрлэе:

  • Яг $2n + p$ ирмэгтэй;
  • Гогцоогүй ба давхар ирмэггүй;
  • Дурын $k$ ($1 ≤ k ≤ n$) бүхэл тооны хувьд, $k$ оройтой дэд граф бүр нь хамгийн ихдээ $2k + p$ ирмэгтэй.

Графын дэд граф гэдэг нь тухайн графын хэд хэдэн оройнууд ба энэ оройнууд дээр төгсгөлтэй ирмэгүүдийн олонлогийг хэлнэ. Чиний даалгавар бол $n$ оройтой $p$-онцлогтой граф олох юм.

Оролт

Эхний мөрөнд тестийн тоог илэрхийлэх $t$ ($1 ≤ t ≤ 5$) гэсэн бүхэл тоо байна. Дараагийн $t$ мөр бүрт $n$, $p$ ($5 ≤ n ≤ 24$; $p ≥ 0$; $2n + p ≤ \frac{n(n-1)}{2}$) тоонууд байна. Уг граф гарцаагүй олддог байна.

Гаралт

$t$ тест бүрт $2n + p$ мөрөнд $p$-огтлолт графын ирмэгүүдийн тайлбарыг хэвлэнэ: $i$ дэх мөрөнд холбогдсон оройн дугаар болох $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}$) тоонуудыг зайгаар тусгаарлан хэвлэнэ. Графын оройнуудыг $1$-ээс $n$ хүртэл дугаарласан гэж үзнэ.

Тест бүрийн хариуг тестүүдийн өгөгдөл дэх дарааллаар хэвлэ. Хэрэв олон хариу байвал аль нэгийг нь хэвлэхэд хангалттай.

Орчуулсан: Бат-Од

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

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