Petunjuk: Kami menyediakan pernyataan singkat dan formal pada paragraf terakhir deskripsi soal.

Di masa depan yang jauh, para fisikawan akhirnya menemukan hukum alam tentang waktu dan sebab-akibat. Bahkan sebelum seseorang lahir, kita dapat mengetahui sebagian informasi tentang kehidupannya melalui analisis teoretis. Dengan kata lain, fisika memungkinkan kita, sampai taraf tertentu, untuk “meramalkan” “takdir” seseorang.

Sederhananya, takdir seseorang adalah sebuah pohon berakar $T$ yang terdiri atas titik-titik waktu: akar pohon melambangkan kelahiran, sedangkan daun melambangkan kematian. Setiap simpul bukan daun $u$ memiliki satu atau lebih anak $v_1,v_2,\ldots,v_{c_u}$, yang mewakili berbagai kemungkinan yang dapat dicapai melalui $c_u$ pilihan berbeda yang dibuat orang tersebut pada waktu yang diwakili oleh $u$. Secara formal, sebuah pilihan adalah sisi $(u,v_i)$ pada pohon, dengan $u$ merupakan orang tua dari $v_i$.

Kehidupan seseorang adalah sebuah lintasan tanpa simpul berulang dari kelahiran (akar) hingga kematian (salah satu daun). Setiap sublintasan dari lintasan ini yang memuat sedikitnya satu sisi merupakan sebuah pengalaman hidup orang tersebut. Semua pengalaman hidup yang dapat diperolehnya dengan menjalani kehidupan melalui segala cara yang mungkin disebut pengalaman hidup potensial. Dengan kata lain, semua pengalaman hidup potensial adalah semua lintasan dari $u$ ke $v$ yang memenuhi $u,v\in T$, $u\ne v$, dan $u$ merupakan leluhur dari $v$. Secara matematis, pengalaman hidup potensial seperti ini dinyatakan sebagai pasangan terurut $(u,v)$, dan himpunan semua pengalaman hidup potensial pada pohon $T$ dinyatakan sebagai $P_T$.

Teori fisika tidak hanya memungkinkan kita mengamati pohon yang mewakili takdir, tetapi juga menganalisis apakah beberapa pengalaman hidup potensial bersifat “penting”. Setiap pilihan yang dibuat seseorang—yaitu setiap sisi pada pohon—dapat bersifat penting atau tidak penting. Sebuah pengalaman hidup potensial disebut penting jika dan hanya jika lintasan yang bersesuaian memuat sebuah sisi yang penting. Kita dapat mengamati bahwa beberapa pengalaman hidup potensial bersifat penting: dengan kata lain, kita dapat memperoleh sebuah himpunan $Q\subseteq P_T$ melalui pengamatan, dengan semua pengalaman hidup potensial $(u,v)\in Q$ bersifat penting.

Bentuk pohon $T$ telah lama ditentukan melalui perhitungan, dan himpunan $Q$ juga telah lama diperoleh melalui pengamatan, sehingga ketidakpastian takdir seseorang telah sangat berkurang. Namun, ketidakpastian yang tersisa masih sangat besar—mari menghitungnya. Untuk pohon $T$ dan himpunan $Q$ yang diberikan, berapa banyak cara berbeda untuk menentukan apakah setiap sisi penting, sehingga memenuhi batasan yang bersesuaian dengan $Q$ yang diamati? Artinya, untuk setiap $(u,v)\in Q$, harus ada sebuah sisi pada lintasan dari $u$ ke $v$ yang ditentukan sebagai penting.

Secara formal: Diberikan sebuah pohon $T=(V,E)$ dan himpunan pasangan simpul $Q\subseteq V\times V$, dengan setiap $(u,v)\in Q$ memenuhi $u\ne v$ dan $u$ merupakan leluhur dari $v$ pada pohon $T$. Di sini, $V$ dan $E$ masing-masing merupakan himpunan simpul dan himpunan sisi pohon $T$. Tentukan banyaknya fungsi berbeda $f:E\to\{0,1\}$ (menetapkan nilai $f(e)$ menjadi $0$ atau $1$ untuk setiap sisi $e\in E$) yang memenuhi syarat berikut: untuk setiap $(u,v)\in Q$, terdapat sebuah sisi $e$ pada lintasan dari $u$ ke $v$ sehingga $f(e)=1$. Karena jawabannya mungkin sangat besar, Anda hanya perlu mencetak hasilnya modulo $998\,244\,353$ (sebuah bilangan prima).

Masukan

Baca data dari berkas destiny.in.

• Baris pertama berisi sebuah bilangan bulat positif $n$, yang menyatakan ukuran pohon $T$. Simpul-simpul pohon diberi nomor dari $1$ sampai $n$, dan simpul $1$ adalah akar.
• Masing-masing dari $n-1$ baris berikutnya berisi dua bilangan $x_i,y_i$ yang dipisahkan oleh spasi, dengan $1\le x_i,y_i\le n$, yang menyatakan adanya sisi antara simpul $x_i$ dan $y_i$ pada pohon. Namun, arah sisi tersebut tidak dijamin.
• Baris berikutnya berisi sebuah bilangan bulat nonnegatif $m$, yang menyatakan banyaknya informasi yang diperoleh melalui pengamatan.
• Masing-masing dari $m$ baris berikutnya berisi dua bilangan $u_i,v_i$ yang dipisahkan oleh spasi, yang menyatakan $(u_i,v_i)\in Q$. Perhatikan: Data masukan dapat memuat informasi yang berulang; dengan kata lain, mungkin terdapat $i\ne j$ dengan $u_i=u_j$ dan $v_i=v_j$.

Lihat tabel di akhir soal untuk ukuran dan batasan data masukan.

Keluaran

Cetak keluaran ke berkas destiny.out.

• Cetak satu baris berisi sebuah bilangan bulat, yaitu banyaknya cara modulo $998\,244\,353$.

Contoh

Masukan 1

5
1 2
2 3
3 4
3 5
2
1 3
2 5

Keluaran 1

10

Catatan

Terdapat $16$ cara secara keseluruhan. Enam cara berikut tidak memenuhi persyaratan soal:

• $(1,2),(2,3),(3,5)$ ditentukan sebagai tidak penting dan $(3,4)$ sebagai penting: tidak ada batasan dalam $Q$ yang terpenuhi.
• $(1,2),(2,3),(3,4),(3,5)$ ditentukan sebagai tidak penting: tidak ada batasan dalam $Q$ yang terpenuhi.
• $(1,2),(2,3)$ ditentukan sebagai tidak penting dan $(3,4),(3,5)$ sebagai penting: batasan $(1,3)$ dalam $Q$ tidak terpenuhi.
• $(1,2),(2,3),(3,4)$ ditentukan sebagai tidak penting dan $(3,5)$ sebagai penting: batasan $(1,3)$ dalam $Q$ tidak terpenuhi.
• $(2,3),(3,5)$ ditentukan sebagai tidak penting dan $(1,2),(3,4)$ sebagai penting: batasan $(2,5)$ dalam $Q$ tidak terpenuhi.
• $(2,3),(3,4),(3,5)$ ditentukan sebagai tidak penting dan $(1,2)$ sebagai penting: batasan $(2,5)$ dalam $Q$ tidak terpenuhi.
• Dalam semua cara lainnya, seluruh batasan dalam $Q$ terpenuhi.

Masukan 2

15
2 1
3 1
4 3
5 2
6 3
7 6
8 4
9 5
10 7
11 5
12 10
13 3
14 9
15 8
6
3 12
5 11
2 5
3 13
8 15
1 13

Keluaran 2

960

Contoh 3

Lihat destiny/destiny3.in dan destiny/destiny3.ans dalam direktori peserta.

Contoh 4

Lihat destiny/destiny4.in dan destiny/destiny4.ans dalam direktori peserta.

Batasan

Seluruh data memenuhi: $n\le 5\times 10^5$, $m\le 5\times 10^5$. Masukan membentuk sebuah pohon, dan untuk $1\le i\le m$, $u_i$ selalu merupakan leluhur dari $v_i$.

Pohon biner lengkap: Dalam soal ini, sebuah pohon yang setiap simpul bukan daunnya memiliki anak kiri dan anak kanan, serta semua daunnya memiliki kedalaman yang sama, disebut pohon biner sempurna. Beri nomor simpul-simpul pohon biner sempurna dari atas ke bawah dan dari kiri ke kanan; pohon yang dibentuk oleh beberapa simpul dengan nomor terkecil disebut pohon biner lengkap.