Ağac

Uğurlu kök ağacında hər bir yarpaq olmayan zirvənin oğullarının sırası müəyyən edilir. Ağaclar izomorfik sayılır, əgər bəzi qarşılıqlı tək-tək uyğunluqla zirvələrin təsviri saxlanılırsa:

• "zirvə s zirvə f-nin oğludur" münasibəti,

• hər bir zirvənin oğullarının sırası.

Verilmişdir sıralanmış kök ağacı T və onun modifikasiyalarının siyahısı. Modifikasiyalar belədir: verilmiş nömrəli zirvəni onun cari valideynindən və onun alt ağacından kəsib, bəzi zirvəyə ən sağ oğul kimi əlavə etmək.

Lazımdır müəyyən etmək, hansı modifikasiyadan sonra ağac ilk dəfə əvvəlki ağaclardan biri ilə izomorfik olur.

Giriş verilənləri

Giriş faylının birinci sətirində iki tam ədəd yazılmışdır: N — ağacda zirvələrin sayı və M — modifikasiyaların sayı (2 ≤ N ≤ 100000, 1 ≤ M ≤ 100000). Ağacın zirvələri təbii ədədlərlə 1-dən N-ə qədər nömrələnmişdir. Ağacın kökü 1 nömrəsinə malikdir.

Növbəti N sətirdə verilmiş ağacın zirvələri üçün sıralanmış oğul siyahıları yazılmışdır. Hər bir i-ci siyahı i-ci zirvənin K_i oğulunun sayı və onun zirvə-oğullarının nömrələrinin ardıcıllığı ilə təsvir edilir (0 ≤ K_i ≤ N–1).

Qalan M sətirdə ağacın modifikasiyaları təsvir edilmişdir. Hər bir modifikasiya iki tam ədəd S_j və F_j ilə müəyyən edilir – zirvənin nömrəsi, hansı ki, onun alt ağacı ilə birlikdə valideynindən kəsilir və hansı zirvəyə ən sağ oğul kimi əlavə edilir (2 ≤ S_j ≤ N, 1 ≤ F_j ≤ N). Zəmanət verilir ki, F_j zirvəsi S_j zirvəsinin nəvəsi deyil və onunla üst-üstə düşmür.

Çıxış verilənləri

Əgər bütün M+1 alınan ağaclar fərqlidirsə, çıxış faylına –1 ədədini yazmaq lazımdır. Əks halda, iki tam ədəd A və B — iki izomorfik ağacın nömrələrini boşluqla yazmaq lazımdır (0 ≤ A < B ≤ M). Əgər izomorfik ağac cütləri bir neçədirsə, B nömrəsi minimal olan cütü yazmaq lazımdır.

Ağaclar aşağıdakı kimi nömrələnir: verilmiş ağac 0 nömrəsinə malikdir. j-ci modifikasiyadan sonra j-ci ağacı alırıq (1 ≤ j ≤ M).

Nümunələr

Qeyd

Aşağıda şərtin birinci testindən bəzi ağaclar verilmişdir.