Yeni Ahırlar#10415
Çiftçi John, inekleri birbirlerine çok yakın olduklarında sık sık kavga ettiklerini fark etti, bu yüzden onları daha uzağa yerleştirmek için yeni bir ahır sırası inşa etmek istiyor.
Çiftçi John her yeni ahır inşa ettiğinde, onu mevcut ahırlardan birine en fazla bir çift yönlü yol ile bağlar. İneklerin birbirinden yeterince uzakta yerleştirildiğinden emin olmak için, bazen verilen bir ahırdan ondan ulaşılabilecek en uzak ahıra olan mesafeyi belirlemek ister (iki ahır arasındaki mesafe, bir ahırdan diğerine ulaşmak için geçilmesi gereken yol sayısıdır).
Çiftçi John toplamda sorgu yapacaktır ve her biri ya bir inşaat sorgusu ya da bir mesafe sorgusudur. Bir inşaat sorgusunda, Çiftçi John bir ahır inşa eder ve onu daha önce inşa edilmiş en fazla bir ahıra bağlar. Bir mesafe sorgusunda, Çiftçi John verilen bir ahırdan, ondan bir dizi yol aracılığıyla ulaşılabilecek en uzak ahıra olan mesafeyi sorar. Sorgulanan ahırın zaten inşa edilmiş olduğu garanti edilir. Çiftçi John'un tüm sorgulara cevap vermesine yardım edin.
İlk satır, sorgu sayısını belirten bir q~(1 \le q \le 10^5) tam sayısı içerir. Sonraki satırın her biri B p veya Q k biçiminde bir sorgu içerir. B p sorgusu, ahırına bağlanan yeni bir ahırın inşa edildiği anlamına gelir; eğer p = -1 ise, yeni ahır başka hiçbir ahıra bağlanmaz, aksi takdirde zaten inşa edilmiş bir ahırın numarasıdır. Q k sorgusu, ahırından ondan ulaşılabilecek en uzak ahıra olan mesafenin bulunmasını gerektirir. Ahırlar inşa edilme sırasına göre 'den başlayarak numaralandırılır: inşa edilen ilk ahır numarasına, ikincisi numarasına sahiptir ve bu şekilde devam eder.
Her mesafe sorgusu için, cevabı ayrı bir satırda yazdırın. Başka hiçbir ahıra bağlı olmayan bir ahır için cevabın olduğuna dikkat edin.
Örnekteki giriş verileri aşağıdaki ahır ağına karşılık gelir:
(1)
\
(2)---(4)
/
(3). sorguda, ahırı inşa edilir. . sorguda, ahırından ondan ulaşılabilecek en uzak ahıra olan mesafe sorulur. ahırı başka hiçbir ahıra bağlı olmadığından, cevap 'dır. . sorguda, ahırına bağlanan ahırı inşa edilir. . sorguda, ahırına bağlanan ahırı inşa edilir. . sorguda, ahırından ondan ulaşılabilecek en uzak ahıra olan mesafe sorulur. Bu durumda en uzak ahır, mesafesinde bulunan ahırıdır. . sorguda, ahırına bağlanan ahırı inşa edilir. . sorguda, ahırından ondan ulaşılabilecek en uzak ahıra olan mesafe sorulur. , ve ahırlarının üçü de ondan mesafesinde olduğundan, cevap 'dir.
Örnek 1