Yet Another XOR Tree Problem

তোমাকে $N$ নোডের একটি ট্রি দেওয়া হয়েছে। ট্রি-র প্রতিটি এজের একটি অঋণাত্মক ওয়েট আছে ।

ধরা যাক, $F(U, V)$ হচ্ছে নোড $U$ এবং নোড $V$ কে সংযোগকারী সিম্পল পথে থাকা সব এজের ওয়েটের $\textbf{XOR}$। সিম্পল পথ হল সেই পথ, যে পথে প্রতিটি নোড সর্বোচ্চ একবার ভিজিট হয় । $F(U, U) = 0$ সব $U$ এর জন্য ।

তোমাকে কিছু ক্যুয়েরী দেওয়া হবে। প্রতিটি ক্যুয়েরীতে দুটি পূর্ণ সংখ্যা $U$ এবং $V$ থাকবে । তোমাকে $F(U, X)$ এর সর্বাধিক মান প্রিন্ট করতে হবে, যেখানে $X$ এমন কোনও নোড যা নোড $U$ এবং নোড $V$ কে সংযোগকারী সিম্পল পথের উপর থাকে ।

ট্রি হচ্ছে একটি আনডিরেক্টেড কানেক্টেড গ্রাফ, যার $N$ টি নোড এবং এক্সাক্টলি $N-1$ টি এজ আছে । এর কোনো সাইকেল নেই এবং এর যেকোনো দুটি নোডের মাঝে শুধুমাত্র একটি সিম্পল পথ আছে ।

$\textbf{XOR}$ হচ্ছে বিটওয়াইজ এক্সর অপারেশন, যাকে “$\oplus$” লজিক সিম্বল দিয়ে প্রকাশ করা হয় । C/C++/Java/Python এ একে “^” অপারেটর দিয়ে প্রকাশ করা হয় ।

Input

ইনপুটের প্রথম লাইনে একটি পূর্ণসংখ্যা $T$, টেস্ট কেসের সংখ্যা থাকবে ।

প্রতি টেস্ট কেসে, প্রথম লাইনে দুটি পূর্ণ সংখ্যা $N, Q$, ট্রিতে নোডের সংখ্যা এবং ক্যুয়েরীর সংখ্যা থাকবে । পরবর্তী $(N-1)$ লাইনের প্রত্যেক লাইনে ৩টি পূর্ণ সংখ্যা $U, V, W (1\leq U, V\leq N; U\neq V; 0\leq W\leq10^9)$ থাকবে, যা নোড $U$ এবং নোড $V$ এর মধ্যবর্তী $W$ ওয়েটের একটি আনডিরেক্টেড এজ প্রকাশ করে । পরবর্তী $Q$ লাইনের প্রত্যেক লাইনে দুটি পূর্ণসংখ্যা $U$ এবং $V (1\leq U, V\leq N)$ থাকবে ।

অবশ্যই এমনভাবে এজ দেওয়া হবে, যাতে এজগুলো দিয়ে একটি ট্রি তৈরি করা যায় ।

স্কোরিং

সাবটাস্ক 1 (10 পয়েন্টস):
$1\leq T\leq100$
$2\leq N, Q\leq 100$

সাবটাস্ক 2 (20 পয়েন্টস):
$1\leq T\leq100$
$2\leq N, Q\leq 1000$

সাবটাস্ক 3 (70 পয়েন্টস):
$1\leq T\leq5$
$2\leq N, Q\leq 10^5$

Output

প্রত্যেক ক্যুয়েরীতে, একটি লাইনে $F(U, X)$ এর সর্বাধিক ভ্যালু প্রিন্ট করবে, যেখানে $X$ এমন কোনও নোড যা নোড $U$ এবং নোড $V$ কে সংযোগকারী সিম্পল পথের উপর থাকে ।

Sample

Input	Output
2 3 4 2 1 17 2 3 10 3 2 3 1 1 2 1 2 4 4 3 1 11 2 3 14 2 4 19 2 2 3 3 1 1 3 4	10 27 17 17 0 0 0 29