Миша Codeforces сайтыг хакерджээ. Тэгээд тэрээр бүх хэрэглэгчдийн нэрийг нь солиулжээ. Одоо хэрэглэгч хэдэн ч удаа нэрээ солиж болно. Гэхдээ шинэ нэр нь хэрэглэгдэж байсан эсвэл хэрэглэдэж байгаа нэртэй ижил байж болохгүй.

Мишад нэр солих хүсэлтүүдийн жагсаалт байгаа. Бүх хүсэлтийг гүйцэлдүүлсний дараа тэрээр хамгийн анхны болон шинэ нэрнүүдийн хоорондох холбоог мэдэхийг хүсчээ. Түүнд туслаарай.

Оролт

Эхний мөрөнд нэр солих хүсэлтийн тоо болох $q$ ($1 ≤ q ≤ 1000$) байна.

Дараагийн $q$ мөр бүрт хүсэлтүүдийн тайлбар байна.

Хүсэлт бүр $old$ ба $new$ гэсэн зайгаар тусгаарлагдсан хоосон биш 2 тэмдэгт мөрөөс бүтнэ. Тэмдэгт мөр нь латин цагаан толгойн том, жижиг үсэгнүүд болон цифрүүдээс бүтнэ. $old$ тэмдэгт мөр нь $new$ тэмдэгт мөрөөс ялгаатай. Тэмдэгт мөрийн урт $20$-оос хэтрэхгүй.

Хүсэлтүүд цаг хугацааны хувьд дарааллаараа байрлана. Өөрөөр хэлбэл хүсэлт ирэх үед $old$ гэсэн нэртэй хүн ганц л байх ба $new$ нэрийг хэн ч хэрэглээгүй байх юм.

Гаралт

Эхний мөрөнд нэрээ сольсон хүний тоо болох $n$-ийг хэвлэ.

Дараагийн $n$ мөрөнд хэрэглэгчдийн хуучин болон шинэ нэрний харгалзааг хэвлэнэ. Мөр бүрт $old$ ба $new$ гэсэн зайгаар тусгаарлагдсан тэмдэгт мөрүүд байх ба энэ нь анх $old$ нэртэй байсан хэрэглэгч $new$ нэртэй болсонг илэрхийлнэ. Гаралтын мөрүүд ямар ч дарааллаар байж болно.

Нэрээ солих хүсэлт гаргасан хэрэглэгч бүр гаралтанд яг нэг удаа хэвлэгдсэн байна.