Runda 35 - Pomidory

Zawody Stałe, runda 35

Limit czasowy: 5s; Limit pamięciowy: 128MB

Pomidory

Hodowla pomidorów to wyczerpujące zajęcie. Na szczęście znajomość reguł zasad dobrego hodowcy to pierwszy krok do osiągnięcia sukcesu. Andrzej jest inteligentnym i wykwalifikowanym rolnikiem z bogatym życiorysem i nikogo w okolicy nie zdziwiło to, że pierwszy zdobył sadzonki nowej odmiary - Pomidora Podczepianego, dającego wyśmienite plony. Jednak aby nabrzmiały sokiem dojrzałe owoce potrzebna jest intentywna pielęgnacja.

Andrzej ma całą instrukcję, w której krok po kroku jest opisane jak należy podczepiać pewne sadzonki pomidora do innych. Ponadto musi wciąż kontrolować, jak daleko od korzenia sadzonki znajdują się pewne ważne owoce. Każda sadzonka Pomidora Podczepianego wygląda jak drzewko -  składa się z pnączy i owoców. Każda sadzonka jest umocowana przy suficie szklarni i na początku instrukcja każe uwiązać tak każdą sadzonkę (składającą się tylko z jednego owocu) osobno. Instrukcje mogą być dwojakiego rodzaju:

1) Odczep jedną z sadzonek od sufitu i podczep ją pnączem do pewnego owocu innej sadzonki.

2) Zbadaj, na jakiej głębokości (jak wiele pnączy trzeba przejść aż do sufitu) znajduje się wskazany owoc.

Innymi słowy, jeśli wyobrazić sobie sadzonki jako drzewa, to instrukcja 1) każe nam podczepić korzeń jednego z drzew do pewnego wierzchołka drugiego drzewa, zaś instrukcja 2) każe nam zbadać głębokość wierzchołka w drzewie. Andzej ma problem z odczytaniem instrukcji, poprosił więc Ciebie o pomoc i znalezienie dla niego odpowiedzi na instrukcje drugiego typu.

Wejście:

Pierwsza linia wejścia zawiera liczby całkowite i - kolejno liczbę początkowych pojedyńczych sadzonek oraz liczbę instrukcji do wykonania (). Załóż, że pomidory, stanowiące początkowe sadzonki, są kolejno ponumerowane od do . W kolejnych liniach znajdują się instrukcje postaci:

1) P  - oznaczające, że należy podczepić całą sadzonkę zawierającą pomidor o numerze do pomidora o numerze . Jeżeli i należą do tej samej sadzonki, instrukcję należy zignorować.

2) D   -  oznaczające, że należy wypisać głębokość pomidora o numerze . Przez głębokość rozumiemy tu odległość pomidora (ile pnączy w górę należy pokonać), aby dotrzeć do sufitu, gdzie sadzonka jest poczepiona.

Wyjście:

Dla każdej instrukcji postaci D należy wypisać, aktualną w momencie pojawienia się instrukcji, głębokość pomidora o numerze w nowej linii.

Przykład:

Wejście:

Wyjście:

Rysunek powyżej prezentuje ostatnie trzy instrukcje, jeśli przyjmniemy, że wierzchołki 6 i 8 oznaczone są niebieskimi okręgami.