Category
Similar Problems

0852. Racing on the Tree

Time limit : 1000 ms
Memory limit : 64 mb

Azat Yusupov hozirda TATU Urganch filiali 4-kurs talabalariga qurilmalarga dastur yozishni o’rgatmoqda. U yaqinda shunday bir qurilma yasadi va uni “Racing on the Tree” deb atadi. Bu qurilma graf ko’rinishida, aniqrog’i daraxt shaklida bo’lib, uning uchlari va qirralari orqali ikkita mashina harakatlanadi. Daraxtning barcha qirralari bir xil uzunlikka ega va ildizi 1-uchda joylashgan bo’lib mashinalar har doim ildizga tomon harakatlanadi. Mashinalar ikkita har xil a va b uchlarga qo’yiladi va ularga o’zgarmas va, vb (qirra / s) tezlik beriladi. Azat Yusupov 4-kurs talabalari Shavkat va Islomga bu mashinalarning qaysi biri marraga (ya’ni ildizga) birinchi bo’lib yetib kelishini aniqlashni topshiriq sifatida berdi. Shavkat va Islom bu masalani osonlik bilan yechishdi. Qurilma mukammal emas edi ya’ni ba’zi bir holatlarda mashinalar bir biri bilan to’qnashib qolar edi. Hozirda Azat Yusupovning bu masala ustida bosh qotirishga vaqti yo’q, shu sababli 4-kurs talabalarini bu muammoni ham hal qilishiga ishonmoqda. Shavkat va Islomga berilgan vazifa bu mashinalarning grafning qaysi nuqtasida uchrashishini topishdan iborat. Ya’ni topshiriq agar mashinalar qirrada to’qnashishsa qirraning tartib raqamini, uchda to’qnashishsa uchning tartib raqamini topishdan iborat. Siz ham bu masalaga urinib ko’ring balki 4-kurslarimizdan oldinroq uni yechimini toparsiz.

Kiruvchi ma’lumotlar: Birinchi qatorda n butun soni daraxtning uchlari soni (1 ≤ n ≤ 105). Keyingi n-1 satrda ikkita butun son u va v butun sonlar i-qirraga yopishgan uchlarning tartib raqami (1 ≤ u, v ≤ n, u != v).

Keyingi qatorda q butun son so’rovlar soni (1 ≤ q ≤ 105). Keyingi q ta satrda so’rovlar beriladi. Har bir so’rovda a, b, va, vb butun sonlar beriladi (1 ≤ a, b ≤ n, a != b, 1 ≤ va, vb ≤ 105).

Chiquvchi ma’lumotlar: q ta satrda har bir so’rov uchun bitta butun son agar mashinalar uchda uchrashishsa “v x” ko’rinishda (bu yerdauchning x uchning tartib raqami), agar qirrada uchrashishsa “e y” ko’rinishda (bu yerda y qirraning tartib raqami), aks holda ular uchrashishmasa “n” chiqaring.

№

Kiruvchi ma’lumotlar

Chiquvchi ma’lumotlar

1

 
10
1 2
1 3
2 4
2 5
5 6
5 7
4 8
3 9
3 10
5
8 5 7 4
6 7 1 1
6 10 3 2
4 6 4 7
2 7 1 10

e 1

v 5

v 1

e 1

e 1

2

 
7
1 2
1 3
3 4
3 5
5 7
2 6
6
6 5 5 5
4 7 100000 200000
3 7 1 5
7 5 300 100
3 2 9 10
6 3 4 2

v 1

v 3

e 2

e 4

n

v 1