A. Цэгцлэх

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

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

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

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

Энэ бодлогоор та хард дискээ цэгцлэх алгоритмыг хэрэгжүүлэх юм. Хард диск 1-ээс $n$ хүртэл дугаарлагдсан кластерийн дарааллуудаас бүрдэнэ. Диск бичигдсэн $m$ файлуудыг агуулах ба $i$ дахь файл нь $a_{i, 1}, a_{i, 2}, ..., a_{i, n_i}$ кластеруудыг эзлэнэ. Эдгээр кластерууд нь диск дээр дарааллан байх албагүй боловч өгөгсдсөн дараалал нь файл дахь дараалалтай нь тохирно ($a_{i, 1}$ кластер нь $i$ дахь файлын эхний хэсгийг агуулна, $a_{i, 2}$ хоёр дахь хэсгийг г.м). Мөн диск ямар файлын хэсгийг агуулаагүй нэг болон хэд хэдэн кластерыг агуулна.

Та $i$ дахь кластерын доторхыг $j$ дахь кластерт хуулах үйлдлийг хийж болно ($i, j$ нь өөр байх ёстой). Мөн хэрэв $j$ дахь кластер ямар нэгэн мэдээллийг хадгалдаг байсан бол тэр нь үүрд устана гэсэн үг. Кластерууд цэвэрлэгддэггүй бөгөөд цэгцлэх үйлдэл дууссаны дараа зарим зүгээр л хэрэглэгдээгүй гэж зарлагддаг (файлуудын зарим нэг хэсгийг агуулж байсан ч гэсэн).

Таны даалгавар бол хуулах үйлдлүүдийн дарааллыг ашиглан файл бүрийг санах ойн дараалсан байрыг эзлүүлэх. Файл бүр дараалсан кластерын хэсгийг эзлэх хэрэгэтэй ба файлууд нь хард дискийн эхлэлээс авхуулан бие биеэ даган байрлана. Цэгцлэсний дараагаар бүх чөлөөт (хэрэглэгдээгүй) кластерууд хард дискийн төгсгөлд байрлана. Цэгцэлсний дараа файлууд нь ямар ч хамаагүй дарааллаар байж болно. Файл бүрийн кластерүүд харин эхнээс төгсгөл хүртэл дарааллан байрлана. Тэмдэглэл дэх тайлбарыг уншина уу.

Диск цэгцлэх үйлдлүүдийн дарааллуудыг хэвлэ. Та үйлдлүүдийн тоог бага байлгах шаардлагагүй боловч $2*n$-ээс хэтрүүлэхгүй.

Оролт

Эхний мөр харгалзан кластеруудын тоо, файлуудын тоо болох $n, m (1 <= n, m <= 200)$ хоёр бүхэл тоо өгөгдөнө. Дараагийн $m$ мөрүүд файлуудын мэдээллийг хадгална. Мөрийн хамгийн эхний тоо бол $i$ дахь файлын эзлэх кластеруудын тоо $n_i (n_i >= 1)$. Дараагаар нь $n_i$ ширхэг $a_{i, 1}, a_{i, 2}, ..., a_{i, n} (1 <= a_{i, j} <= n)$ тоонууд дагалдана. Кластерийн дугаар болгон ганцхан удаа л орж ирэх нь баталгаатай ба $\sum{i = 1}{m}{n_i} < n$ нь дор хаяж нэг хэрэглэгдээгүй кластер байна гэсэн үг. Мөр болгоны тоонууд нь хоосон зайнуудаар тусгаарлагдана.

Гаралт

Дискийг цэгцлэхэд шаардагдах үйлдлүүдийн тоог заах ганц бүхэл тоо $k (0 <= k <= 2*n)$-г эхний мөрөнд хэвлэнэ. Дараагийн $k$ ширхэг мөрүүд нь "i j" ($i$ дугаар кластерийн доторхыг $j$ дэх кластерт хуулсан) тоонуудаар дүрсэлсэн үйлдлийг агуулна.

Орчуулсан: devman

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

Оролт
7 2
2 1 2
3 3 4 5
Гаралт
0
Оролт
7 2
2 1 3
3 2 4 5
Гаралт
3
2 6
3 2
6 3

Тэмдэглэл

Диск найман кластер, хоёр файлаас тогтдог гэж саная. Эхний файл хоёр кластерыг эзлэх бол хоёр дахь файл гурван кластерыг эзлэнэ. Цэгцэлсний дараа файлуудын зөв болон бураа байрлалуудын жишээг харцгаая.

% zurag

Жишээ 2: Файл болгон санах ойд дарааллан байрлах ёстой.

Жишээ 3: Файлуудын бие биетэйгээ үүсгэх дарааллууд нь чухал биш, эхлээд хоёр дугаар файл бичигдэж дараагаар нь нэг дүгээр файл.

Жишээ 4: Файлуудын хэсгийн дарааллуудыг зөрчиж болохгүй.

Жишээ 5: Хэрэглэгдээгүй кластерүүд дискийн төгсгөлд байх хэрэгтэй бөгөөд уг жишээнд хэрэглэгдээгүй кластерууд нь 3, 7, 8 байна.

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