A. Найзууд уу эсвэл?

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

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

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

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

Поликарпус-д нэгэн хобби байдаг ба энэ нь ховор олон нийтийн сүлжээг хөгжүүлэх юм. Түүний ажил бараг дуусаж байгаа ба одоо ганцхан модул хэрэгжүүлэх дутуу байгаа юм. Уг модул нь найзуудыг тодорхойлдог модул байв. Өө нээрээ уг олон нийтийн сүлжээнд хэн нэгэн найзуудаа нэмэхдээ өөрөө нэмдэггүй! Найзуудын хосууд нь дараах аргаар дүгнэгдэнэ. $A$ хэрэглэгч $B$ хэрэглэгч уруу $t_{1}$ цагт захиа илгээсэн ба $B$ хэрэглэгч $A$ хэрэглэгч уруу $t_{2}$ цагт захиа илгээсэн гэж үзье. Хэрэв $0 < t_{2} - t_{1} ≤ d$ бол $B$ хэрэглэгчийн захиа нь $A$ хэрэглэгчийн захианы хариу байх юм. Хэрэв $A$ нь $B$-ын дор хаяж нэг захианд хариулсан эсвэл $B$ нь $A$-ын дор хаяж нэг захианд хариулсан байвал $A$ болон $B$-г найзууд гэж үзнэ.

Танд цаг хугацааны дарааллаараа байх захиануудын бүртгэл болон $d$ тоо өгөгдөв. Найзууд байх бүх хэрэглэгчдийн хосуудын тоог олно уу.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $d$ ($1 ≤ n, d ≤ 1000$) өгөгдөнө. Дараагийн $n$ мөрөнд захиануудын бүртгэл өгөгдөнө. $i$-дахь мөрөнд "$A_{i}$ $B_{i}$ $t_{i}$" (хашилтгүйгээр) хэлбэр бүхий бүртгэлийн мөр өгөгдөх ба энэ нь $A$ хэрэглэгч $B$ хэрэглэгч уруу $t_{1}$ цагт захиа илгээсэн гэсэн үг юм. $A_{i}$ болон $B_{i}$ нь хамгийн ихдээ $20$ тэмдэгт бүхий урттай хоосон биш тэмдэгт мөрүүд байх ба жижиг үсгүүд ('$a$' ... '$z$')-ээс тогтсон байна. $t_{i}$ нь бүхэл тоо байна ($0 ≤ t_{i} ≤ 10000$). Эдгээр мөрүүд нь $t_{i}$-ууд ихсэх дарааллаар өгөгдөх ба ямар ч хэрэглэгч өөртөө захиа илгээгээгүй байна. Мөрнүүдэд байх элементүүд нь зайгаар тусгаарлагдсан байна.

Гаралт

Эхний мөрөнд хос найзуудын тоо болох бүхэл тоо $k$-г хэвлэнэ. Дараагийн $k$ мөрөнд хос найзуудыг "$A_{i}$ $B_{i}$" (хашилтгүйгээр) хэлбэртэйгээр хэвлэнэ. Та хос доторх хэрэглэгчид болон тэдгээр хосуудыг ямар ч дарааллаар хэвлэж болно. Хос бүр нь яг нэг удаа хэвлэгдсэн байна.

Орчуулсан: Баатархүү

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

Оролт
4 1
vasya petya 1
petya vasya 2
anya ivan 2
ivan anya 4
Гаралт
1
petya vasya
Оролт
1 1000
a b 0
Гаралт
0

Тэмдэглэл

Эхний жишээнд Vasya болон Petya нь найзууд байна. Учир нь тэдгээрийн захиануудын явуулсан хугацаа нь нэг секундийн зөрүүтэй байгаа юм. Anya болон Ivan нь найзууд биш байна. Учир нь тэдгээрийн захиануудын явуулсан хугацаа нь нэг секундээс илүү зөрүүтэй байгаа юм.

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