SPOJ in Armenian

Դուք ընդգրկված եք մի խմբում, որը համալսարանի ուսանողների համար պետք է web2.0 կիրառություն ստեղծի։ Գործածողները (users) պետք է հնարավորություն ունենան գրանցվել և նշել, թե մյուս գործածողներից ովքեր են իրենց ընկերները։ Ընկերության վերաբերյալ տվյալների միջոցով կարելի է սահմանել ընկերության գրաֆ։

Եթե գործածողներից մեկը բացում է մյուսի էջը, կիրառությունը պետք է պարզի, ընկերության գրաֆում առաջինից երկրորդը տանող ճանապարհ կա, թե ոչ։ Եթե կա այդպիսի ճանապարհ, ապա այն պետք է պատկերվի։

Խումբն արդեն նախագծել է կիրառությունը, բայց երբ այն մասսայական դարձավ, պարզվեց, որ ընկերության ճանապարհի հաշվարկը շատ դանդաղ է արվում։ Խմբի ղեկավարը որոշել է նախ պարզել ընկերության ճանապարհի գոյությունը, ապա նոր անել նրա հաշվարկը։ Ընկերության ճանապարհի գոյության խնդիրը հանձնարարված է ձեզ։ Եվ նրա լուծումը պետք է բավականին արագ լինի։

Խնդիրը

Տրված է գործածողների քանակը, ինֆորմացիան, թե որ գործածողներն են ընկերներ։ Բացի այդ տրված են նաև գործածողների զույգեր, որոնցից յուրաքանչյուրի համար ձեր ծրագիրը պետք է պարզի, թե գոյություն ունի, արդյոք, ընկերության գրաֆում նրանց միացնող ճանապարհ։

Մուտք

Առաջին տողում տրված է գործածողների n (1 <= n <= 1 000 000) քանակը։ Հաջորդ տողում տրված է k (1 <= k <= 100 000) ընկերներ հանդիսացող զույգերի քանակը։ Հաջորդ k տողերից յուրաքանչյուրում տրված են երկու a և b թվեր, որոնք ցույց են տալիս, որ a և b համարի գործածողներն ընկերներ են։ Հաջորդ տողում տրված է հարցումների m քանակը (1 <= m <= 100 000)։ Հաջորդ m տողերից յուրաքանչյուրում տրված է մի թվազույգ։ Յուրաքանչյուր (u, v)  թվազույգի համար պետք է պարզել, թե ընկերության գրաֆում u և v գագաթների միջև ճանապարհ կա, թե ոչ։

Ելք

Ելքում յուրաքանչյուր հարցման համար հարկավոր է արտածել մեկ տող։ Եթե հարցվող գործածողների համար ընկերության գրաֆում ճանապարհ գոյություն ունի, պետք է արտածել 1, հակառակ դեպքում, պետք է արտածել 0։

Օրինակ

Մուտք
5
3
0 1
1 2
3 4
2
0 2
1 3

Ելք
1

0