Negatif olmayan bir tam sayısının ikilik gösterimindeki bir olan bitlerin sayısını ile gösterelim.
Size köşeli bir ağaç ve bir tam sayısı veriliyor. Her köşesi için aşağıdaki problemi düşünün.
köşesi ağacın köküdür. Ona 2^m-1 sayısı atanır, diğer her köşeye ise ile 2^m-1 arasında (uçlar dahil) bir tam sayı atanır. , kökten köşesine giden yol üzerindeki sayıların, yolun her iki ucu da dahil olmak üzere, bit düzeyinde AND'i olsun.
Kök olmayan tüm köşeleri için \operatorname{popcount}(\operatorname{AND}(v)) değeri aynı ise, atama çekici olarak adlandırılır. Her olası kök için çekici atamaların sayısını moduna göre bulun.
n=1 ise, tek atama çekici kabul edilir.
İlk satırda test sayısını belirten bir tam sayısı (1\le t\le10^4) verilir.
Her testin ilk satırında iki tam sayı ve (1\le n,m\le10^5) verilir.
Sonraki n-1 satırın her birinde bir kenarın uçlarını belirten iki tam sayı ve (1\le u,v\le n) verilir. Verilen kenarların bir ağaç oluşturduğu garanti edilir.
Tüm testler üzerinden değerlerinin toplamı 10^5'i aşmaz. değerlerinin toplamı da 10^5'i aşmaz.
Her test için tam sayı içeren bir satır yazdırın. -inci sayı, kökü köşesinde olan çekici atamaların moduna göre sayısına eşit olmalıdır.
Örnek 1
Örnek 2
Örnek 3
Birinci örneğin birinci testinde ağacın tek bir köşesi vardır, bu yüzden cevap 'dir.
Birinci örneğin ikinci testinde köke sayısı atanır. Diğer köşeye , veya sayılarından herhangi biri atanabilir, bu yüzden her iki kök için de cevap 'tür.
Alt görev ( puan): t\le10, n,m\le5.
Alt görev ( puan): n,m\le20.
Alt görev ( puan): her köşenin derecesi en fazla 'dir.
Alt görev ( puan): ağaç bir yıldızdır, yani diğer tüm köşelere komşu olan bir köşe vardır.
Alt görev ( puan): n,m\le1000, \sum n\le5000, \sum m\le5000.
Alt görev ( puan): ek kısıt yoktur.