C. Миша ба ой

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

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

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

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

Ой гэдгээр чиглэлгүй, циклгүй (мөн гогцоо болон зэрэгцээ ирмэггүй) графыг ойлгоё. Нэг удаа Миша $n$ оройтой Ой-гоор тоглож гэнэ. $v$ орой бүрт $degree_{v}$ ба $s_{v}$ ($0 ≤ v ≤ n-1$) гэсэн хоёр бүхэл тоо бичжээ. Эхний тоо нь $v$-тэй хөрш оройн тоо, харин дараагийн тоо нь $v$-тэй хөрш оройн дугааруудын XOR нийлбэр байг. (Хэрэв хөрш орой байхгүй бол $0$ гэж бичнэ).

Дараагийн өдөр нь Миша анх ямар граф байсныг мартчихжээ. Гэхдээ Мишад $degree_{v}$, $s_{v}$ гэсэн утгууд байгаа аж. Түүнд анхны графын ирмэгийн тоо болон ирмэгүүдийг олоход нь туслаарай. Түүнд байгаа тоонуудад харгалзах Ой үргэлж олдоно гэж мэдэгдэж байгаа.

Оролт

Эхний мөрөнд графын оройн тоо болох $n$ ($1 ≤ n ≤ 2^{16}$) байна.

Дараагийн $i$ дүгээр мөрөнд $degree_{i}$ ба $s_{i}$ ($0 ≤ degree_{i} ≤ n - 1$, $0 ≤ s_{i} < 2^{16}$) тоонууд зайгаар тусгаарлагдан байрлана.

Гаралт

Эхний мөрөнд графын ирмэгийн тоо болох $m$-ийг хэвлэ.

Дараагийн $m$ мөр тус бүрт $(a, b)$ ирмэгт харгалзах оройнуудын дугаар буюу $a$ ба $b$ ($0 ≤ a ≤ n - 1$, $0 ≤ b ≤ n - 1$) гэсэн тоонуудыг хэвлэ.

Ирмэгүүд дурын дарааллаар хэвлэгдэж болно. Ирмэгийн оройнууд мөн дурын дарааллаар хэвлэгдэж болно.

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

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

Оролт
3
2 3
1 0
1 0
Гаралт
2
1 0
2 0
Оролт
2
1 1
1 0
Гаралт
1
0 1

Тэмдэглэл

Тоонуудыг XOR үйлдлээр нэмэх гэдэг нь тооны харгалзах бит бүрийн хувьд нэмээд хоёрт хуваах үйлдэл хийхийг хэлэх юм. Энэ үйлдэл орчин үеийн олон программын хэлэнд бий. Жишээ нь C++, Java болон Python хэлнүүдэд энэ үйлдэл "^" гэж тэмдэглэгдэнэ. Харин Pascal хэлэнд "xor" гэж тэмдэглэгддэг.

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