Qrafiklərin hasilatı#1750
Verilmiş istiqamətli döngəsiz qraf var. Qraf üzərində standart oyun aşağıdakı kimidir: əvvəlcə jeton qrafın bir zirvəsinə qoyulur (buna başlanğıc mövqeyi deyilir). İki oyunçu növbə ilə jetonu qrafın kənarları boyunca hərəkət etdirir. Heç bir hərəkət edə bilməyən oyunçu uduzur.
Oyun nəzəriyyəsində tez-tez daha mürəkkəb oyunlar da nəzərdən keçirilir. Məsələn, iki qraf üzərində oyunların düz məhsulu (direct product). Düz məhsul oyunu belə təyin olunur: əvvəlcə hər iki qrafda öz başlanğıc mövqeyində jeton yerləşdirilir. Hər gedişdə oyunçu hər iki jetonu kənarları boyunca hərəkət etdirir (hər jeton öz qrafının daxilində hərəkət edir). Heç bir hərəkət edə bilməyən oyunçu uduzur — yəni, ən azı bir oyunda hərəkət edə bilməyən oyunçu uduzur.
Sizin vəzifəniz optimal oyun zamanı kimin qalib gələcəyini müəyyən etməkdir.
Birinci sətirdə N_1 və M_1 tam ədədləri verilir — birinci qrafda zirvələrin və kənarların sayı (1 \leq N_1, M_1 \leq 100000). Sonrakı M_1 sətrin hər birində iki tam ədəd və verilir (1 \leq x, y \leq N_1).
Bundan sonra ikinci qraf eyni formatda M_2 + 1 sətirdə təsvir edilir.
Girişin sonunda başlanğıc zirvələrin cütlərinin siyahısı verilir. Bu sətrlərdən birincisində (1 \leq T \leq 100000) — başlanğıc zirvələr cütlərinin sayı verilir. Sonrakı sətrin hər birində iki ədəd v_1 və v_2 verilir (1 \leq v_1 \leq N_1, 1 \leq v_2 \leq N_2).
Hər bir başlanğıc zirvələr cütü üçün optimal oyunda birinci oyunçunun qalib gəldiyi halda "first", əks halda "second" sətrini çap edin.
Nümunə 1