ডোমকি নামে একটি রাজ্য আছে। ডোমকিতে N টি শহর এবং N - 1 টি দ্বি-মুখী রাস্তা রয়েছে। প্রতিটি শহর 1, 2, 3, ... N নম্বর দিয়ে চিহ্নিত করা হয়েছে । ডোমকির শহরগুলি একে অপরের সাথে এমনভাবে সংযুক্ত যে এটির গঠন একটি [ট্রি](https://en.wikipedia.org/wiki/Tree_(graph_theory) এর মত হয়। ডোমকি-র প্রতিটি শহরকে একটি রাঙ্কিং আছে, যা একটি পূর্ণসংখ্যা।
সম্প্রতি রাজ্যের Tournament Planning Committee(TPC) রাজ্যে কার রেস এর আয়োজন করার সিদ্ধান্ত নিয়েছে। এই টুর্নামেন্টে, সারা বিশ্বের রেসারদের অংশ নিতে আমন্ত্রন করা হয়েছে। তাই টুর্নামেন্টটি সফল্ভাবে শেষ করতে TPC কিছুটা চিন্তিত কারণ একটি টুর্নামেন্ট সফলভাবে শেষ করা সহজ কাজ নয়।
সবচেয়ে বড় সমস্যাটি হল রেসটি যেখানে অনুষ্ঠিত হবে সেই ট্র্যাকগুলি সম্পর্কে তথ্য সগ্রহ করা। তাই তারা টুর্নামেন্ট শুরুর আগে ট্র্যাকগুলির বিস্তারিত তথ্য জানতে আগ্রহী।
দ্রষ্টব্য, একটি ট্র্যাক এক বা একাধিক রাস্তা নিয়ে গঠিত। আরও ভাল বোঝার জন্য, তুমি ট্র্যাকটিকে ডোমকিতে যেকোন দুটি শহরের মধ্যে সবচেয়ে কম দুরত্বের পথ হিসাবে বিবেচনা করতে পার।
চল ট্র্যাক সম্পর্কে আরও একটি জিনিস পরিচয় করিয়ে দেই।
ধর, একটি ট্র্যাকের জন্য TPC দুটি শহর a এবং b নির্ধারণ করেছে যেখানে a হল ট্র্যাক যে শহরে শুরু হয়েছে সেই শহরের নাম্বার এবং b হল ট্র্যাক যে শহরে শেষ হয়েছে সেই শহরের নাম্বার এবং এই ট্র্যা্ককে বলা হয় Tab । একটি ট্র্যাক Tab এর জন্য, যদি আমরা ট্র্যাক Tab তে থাকা সমস্ত রাঙ্কিং নাম্বার সংরক্ষণ করি এবং সেগুলি ক্রমানুসারে একটি কাগজে লিখে রাখি,
তাহলে এটি একটি অ্যারে এর মত হবে এবং TPC এই অ্যারেটিকে Rank Array of the track ab, (RA(a,b)) বলে।
তারা মূলত ডোম্কি রাজ্যের ট্র্যাকগুলো সম্পর্কে তিনটি গুরুত্বপূর্ণ তথ্য জানতে চায়।
তারা নীচের মতো একটি কাঠামোগত উপায়ে তাদের জানতে চাওয়া তথ্যগুলো তালিকাভুক্ত করেছেন।
আরও ভাল বুঝতে, দয়া করে স্যাম্পল কেসের ব্যাখ্যা দেখতে পার।
এদিকে, TPC জানতে পেরেছে যে তুমি তোমার দেশের একজন দুর্দান্ত প্রোগ্রামার,
এবং তারা তোমাকে এই কাজটির জন্য নিয়োগ দেওয়ার পরিকল্পনা করছে।
এখন প্রশ্ন হল, তুমি কি ট্র্যাকগুলি সম্পর্কিত প্রশ্নের উত্তর দিয়ে তাদের সহায়তা করতে পার?
প্রথমে একটি পুর্ণসংখ্যা T (T <= 10) দেয়া থাকবে যেটা টেস্ট কেস সংখ্যা বুঝায়।
প্রতিটি টেস্ট কেস এর শুরুতে একটি পুর্ণসংখ্যা N (1 ≤ N ≤ 2×105) থাকবে যা ডোমকি রাজ্যে কতগুলো শহর আছে তা বুঝায়।
এরপর N টি পুর্ণসংখ্যা r1, r2, r3 ... rN থাকবে যা শহরগুলোর রাঙ্কিং বুঝায় যেখানে প্রতিটা i (1 ≤ i ≤ N) এর জন্য ri (1 ≤ ri ≤ 60) হচ্ছে i তম শহরের রাঙ্কিং।
এরপর N - 1 টি লাইন থাকবে যার প্রতিটা লাইনে দুটি করে পুর্ণসংখ্যা u, v থাকবে যার মানে হচ্ছে u এবং v এর মধ্যে একটি দ্বিমুখী রাস্তা রয়েছে।
এরপর একটি পুর্ণসংখ্যা Q(1 ≤ Q ≤ 2×105) থাকবে যা TPC কতগুলো প্রশ্ন করবে তা বুঝায়।
এরপর Q টি লাইনের প্রতিটিতে 1, 2 বা 3 নাম্বার ধরনের একটি প্রশ্ন থাকবে।
এটা নিশ্চিত যে দুটি শহরের মধ্যে এক এর অধিক রাস্তা থাকবে না এবং যেকোন শহরে নিজের সাথে কোন রাস্তা থাকবেনা
সবগুলো কেসের N এর যোগফল 400000 এর বেশি হবেনা এবং Q এর যোগফল 550000 এর বেশি হবেনা।
#Subtask Constraints
subtask# 1 (30 পয়েন্ট)
শুধু type 1 কুয়েরি থাকবে।
একটি শহর সর্বোচ্চ ২ টি আলাদা শহরের সাথে সরাসরি যুক্ত থাকবে।
1 ≤ N, Q ≤ 1000
1 ≤ ri ≤ 30.
সবগুলো কেসের N এর যোগফল 4000 এর বেশি হবেনা।
সবগুলো কেসের Q এর যোগফল 4000 এর বেশি হবেনা।
subtask# 2 (70 পয়েন্ট)
Original Constraint.
প্রতিটি টেস্টকেস এর শুরুতে টেস্টকেস নাম্বার প্রিন্ট করতে হবে এবং এরপর প্রতিটি নতুন লাইন এ প্রশ্নগুলোর উপর নির্ভর করে "YES" অথবা "NO" (উদ্ধৃতি চিহ্ন ব্যতিত) প্রিন্ট করতে হবে।
ভালভাবে বোঝার জন্য স্যাম্পল কেস দেখ
Input | Output |
---|---|
1 8 1 3 2 2 3 2 2 1 8 5 6 2 5 2 3 1 1 4 1 2 2 7 6 1 5 6 1 6 8 2 1 8 2 5 7 3 3 8 4 8 3 4 5 3 7 | Case 1: YES NO YES NO YES NO |
ডোমকি রাজ্যের গাঠনিক চিত্র -
চ
query - 1 এ, RA(5,6) = {3, 3, 2}. উপাদানগুলো পুনরায় সাজিয়ে আমরা RA(5,6) = {3, 2, 3} বানাতে পারি যা একটি প্যালিন্ড্রম। তাই উত্তর হবে "YES".
query - 2 এ, RA(6,8) = {2, 3, 3, 1}. উপাদানগুলো পুনরায় সাজিয়ে বা না সাজিয়ে আমরা কোন ভাবেই এটাকে প্যালিন্ড্রম বানাতে পারবনা। তাই উত্তর "NO".
query - 3 এ, RA(1,8) = {1, 3, 3, 1} যা একটি প্যালিন্ড্রম. তাই উত্তর হবে "YES".
query - 4 এ, RA(5,7) = {3, 3, 2} যা একটি প্যালিন্ড্রম. তাই উত্তর হবে "NO".
query - 5 এ, RA(3,8) = {2, 1, 3, 3, 1} এবং RA(4,8) = {2, 1, 3, 3, 1}. এখানে RA(3,8) এবং RA(4,8) এর সাইজ সমান এবং প্রতিটা i (1 ≤ i ≤ size(RA(3,8))) এর জন্য, RA(3,8)[i] == RA(4,8)[i]. তাই RA(3,8) এবং RA(4,8) অনুরুপ.লক্ষ্য করো, আমরা দুইটা অ্যারেতেই ১ থেকে ইন্ডেক্স করাশুরু করেছি .