C. Диагоналын доогуур

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

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

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

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

Танд $n$ мөр $n$ баганатай матриц өгөгдсөн. Бид мөр болон багануудийг 1-ээс $n$ хүртэл дугаарласан гэж үзье. Матрицийн зарим нүднүүд (нийт $n - 1$ байна) 1 байна. Бусад нь бүгд 0 байна. Бид дараах үйлдлийг матрицад хийж чадна:

  • $i$ болон $j$ дэх мөрийг солих.
  • $i$ болон $j$ дэх баганыг солих.

Таны даалгавар бол дээрх 2 үйлдлийг ашиглан матрицийг тусгай хэлбэртэй болгох юм. Тусгай хэлбэр гэдэг нь матрицийн бүх нэгийн тоо диагоналийн доогуур байна. Матрицийн $i$, $j$ 2-ын огтлолцол дээр орших нүднүүдийн $i > j$ нүднүүдийг диагоналиас доор байна гэж үзнэ.

Оролт

Эхний мөрөнд мөр баганы тоог илтгэх $n$ ($2 ≤ n ≤ 1000$) тоо өгөгднө. Дараагийн $n - 1$ мөрөнд 1-үүдийн байрлалууд өгөгдөнө. Байрлал бүрийг $x_k$ $y_k$ ($1 ≤ x_k, y_k ≤ n$) тоонууд тодохойлно.

Бүх нэгийн байршил өөр байна.

Гаралт

Хийсэн үйлдлүүдийг дарааллыг хэвлэнэ. Энэ үйлдлүүдийг хийснээр матриц нь тусгай хэлбэртэй болох ёстой.

Эхний мөрөнд нийт хийх үйлдлийн тоо болох $m$ -ийг ($m ≤ 10^5$) хэвлэнэ. Дараагийн $m$ мөр бүрт $t, i, j$ ($1 ≤ t ≤ 2, 1 ≤ i, j ≤ n, i ≠ j$) тоонууд өгөгдөнө. $t = 1$ байвал мөрийг солино. $t = 2$ байвал баганыг солино. $i, j$ хоёр нь дугааруудыг нь илтгэнэ.

Жич хйих үйлдлийн тоогоо багасгах хэрэгтэйг анхаарна уу. Гэхдээ нийт үйлдлийн тоо $10^5$-аас хэтрэх ёсгүй. Хэрэв олон шийдтэй бол хүссэн нэгээ хэвлэ.

Орчуулсан: Энхсанаа

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

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