Gợi ý: Ở đoạn cuối của phần mô tả bài toán, chúng tôi cung cấp một phát biểu ngắn gọn và hình thức hóa.

Trong tương lai xa, các nhà vật lý cuối cùng đã khám phá ra những quy luật tự nhiên của thời gian và quan hệ nhân quả. Ngay cả trước khi một người được sinh ra, chúng ta cũng có thể biết một số thông tin về cuộc đời của người đó thông qua phân tích lý thuyết. Nói cách khác, vật lý cho phép chúng ta “tiên đoán” “số phận” của một người ở một mức độ nhất định.

Nói đơn giản, số phận của một người là một cây có gốc $T$ gồm các thời điểm: đỉnh gốc biểu thị sự ra đời, còn các đỉnh lá biểu thị cái chết. Mỗi đỉnh không phải lá $u$ có một hoặc nhiều đỉnh con $v_1,v_2,\ldots,v_{c_u}$, biểu thị những khả năng khác nhau mà $c_u$ lựa chọn khác nhau của người đó tại thời điểm được biểu diễn bởi $u$ có thể dẫn đến. Một cách hình thức, một lựa chọn là một cạnh $(u,v_i)$ trên cây, trong đó $u$ là cha của $v_i$.

Cuộc đời của một người là một đường đi không lặp đỉnh từ lúc sinh ra (tức đỉnh gốc) đến lúc chết (tức một đỉnh lá). Mọi đường đi con chứa ít nhất một cạnh của đường đi này đều là một trải nghiệm cuộc đời của người đó. Tất cả những trải nghiệm cuộc đời mà người đó có thể có khi sống cuộc đời theo mọi cách có thể được gọi là trải nghiệm cuộc đời tiềm năng. Nói cách khác, các trải nghiệm cuộc đời tiềm năng là tất cả các đường đi từ $u$ đến $v$ thỏa mãn $u,v\in T$, $u\ne v$ và $u$ là tổ tiên của $v$. Trong toán học, một trải nghiệm cuộc đời tiềm năng như vậy được ký hiệu bằng cặp có thứ tự $(u,v)$; tập hợp tất cả các trải nghiệm cuộc đời tiềm năng của cây $T$ được ký hiệu là $\mathcal{P}_T$.

Lý thuyết vật lý không chỉ cho phép chúng ta quan sát cây biểu diễn số phận, mà còn cho phép phân tích xem một số trải nghiệm cuộc đời tiềm năng có “quan trọng” hay không. Mỗi lựa chọn của một người — tức mỗi cạnh trên cây — đều có thể quan trọng hoặc không quan trọng. Một trải nghiệm cuộc đời tiềm năng được gọi là quan trọng khi và chỉ khi trên đường đi tương ứng có một cạnh quan trọng. Chúng ta có thể quan sát được rằng một số trải nghiệm cuộc đời tiềm năng là quan trọng: nói cách khác, chúng ta có thể quan sát được một tập hợp $\mathcal{Q}\subseteq\mathcal{P}_T$ sao cho mọi trải nghiệm cuộc đời tiềm năng $(u,v)\in\mathcal{Q}$ đều quan trọng.

Hình dạng của cây $T$ đã được tính toán xác định từ lâu, và tập hợp $\mathcal{Q}$ cũng đã được quan sát từ lâu; tính bất định trong số phận của một người đã giảm đi rất nhiều. Nhưng tính bất định vẫn còn rất lớn — hãy tính xem: với cây $T$ và tập hợp $\mathcal{Q}$ cho trước, có bao nhiêu cách khác nhau để xác định mỗi cạnh có quan trọng hay không sao cho thỏa mãn các ràng buộc tương ứng với $\mathcal{Q}$ đã quan sát được: với mọi $(u,v)\in\mathcal{Q}$, có một cạnh trên đường đi từ $u$ đến $v$ được xác định là quan trọng.

Phát biểu hình thức: Cho một cây $T=(V,E)$ và tập hợp các cặp đỉnh $\mathcal{Q}\subseteq V\times V$, thỏa mãn với mọi $(u,v)\in\mathcal{Q}$, ta có $u\ne v$ và $u$ là tổ tiên của $v$ trên cây $T$. Ở đây $V$ và $E$ lần lượt biểu thị tập đỉnh và tập cạnh của cây $T$. Hãy tìm số hàm khác nhau $f:E\to\{0,1\}$ (gán giá trị $f(e)$ bằng $0$ hoặc $1$ cho mỗi cạnh $e\in E$) thỏa mãn: với mọi $(u,v)\in\mathcal{Q}$, tồn tại một cạnh $e$ trên đường đi từ $u$ đến $v$ sao cho $f(e)=1$. Vì đáp án có thể rất lớn, bạn chỉ cần in phần dư của kết quả khi chia cho $998\,244\,353$ (một số nguyên tố).

Dữ liệu vào

Đọc dữ liệu từ tệp destiny.in.

• Dòng đầu tiên chứa một số nguyên dương $n$, biểu thị kích thước của cây $T$. Các đỉnh được đánh số từ $1$ đến $n$, và đỉnh $1$ là gốc.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số $x_i,y_i$ cách nhau bởi dấu cách, thỏa mãn $1\le x_i,y_i\le n$, biểu thị rằng có một cạnh giữa các đỉnh $x_i$ và $y_i$ trên cây; không có bảo đảm về hướng của cạnh này.
• Dòng tiếp theo chứa một số nguyên không âm $m$, biểu thị số thông tin đã quan sát được.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số $u_i,v_i$ cách nhau bởi dấu cách, biểu thị $(u_i,v_i)\in\mathcal{Q}$. Lưu ý: Dữ liệu vào có thể chứa thông tin lặp lại; nói cách khác, có thể tồn tại $i\ne j$ sao cho $u_i=u_j$ và $v_i=v_j$.

Xem bảng ở cuối bài để biết quy mô và giới hạn của dữ liệu vào.

Dữ liệu ra

Ghi kết quả vào tệp destiny.out.

• In một số nguyên trên một dòng duy nhất, là phần dư của số cách khi chia cho $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

10

Ghi chú

Có tổng cộng $16$ cách, trong đó $6$ cách sau đây không thỏa mãn yêu cầu:

• $(1,2),(2,3),(3,5)$ được xác định là không quan trọng, $(3,4)$ là quan trọng: không ràng buộc nào trong tập hợp $\mathcal{Q}$ được thỏa mãn.
• $(1,2),(2,3),(3,4),(3,5)$ được xác định là không quan trọng: không ràng buộc nào trong tập hợp $\mathcal{Q}$ được thỏa mãn.
• $(1,2),(2,3)$ được xác định là không quan trọng, $(3,4),(3,5)$ là quan trọng: ràng buộc $(1,3)$ trong tập hợp $\mathcal{Q}$ không được thỏa mãn.
• $(1,2),(2,3),(3,4)$ được xác định là không quan trọng, $(3,5)$ là quan trọng: ràng buộc $(1,3)$ trong tập hợp $\mathcal{Q}$ không được thỏa mãn.
• $(2,3),(3,5)$ được xác định là không quan trọng, $(1,2),(3,4)$ là quan trọng: ràng buộc $(2,5)$ trong tập hợp $\mathcal{Q}$ không được thỏa mãn.
• $(2,3),(3,4),(3,5)$ được xác định là không quan trọng, $(1,2)$ là quan trọng: ràng buộc $(2,5)$ trong tập hợp $\mathcal{Q}$ không được thỏa mãn.
• Với các cách còn lại, mọi ràng buộc trong tập hợp $\mathcal{Q}$ đều được thỏa mãn.

Dữ liệu vào 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

Dữ liệu ra 2

960

Ví dụ 3

Xem các tệp destiny/destiny3.in và destiny/destiny3.ans trong thư mục dành cho thí sinh.

Ví dụ 4

Xem các tệp destiny/destiny4.in và destiny/destiny4.ans trong thư mục dành cho thí sinh.

Giới hạn

Mọi dữ liệu đều thỏa mãn: $n\le 5\times10^5$, $m\le 5\times10^5$. Dữ liệu vào tạo thành một cây, và với $1\le i\le m$, $u_i$ luôn là tổ tiên của $v_i$.

Cây nhị phân hoàn chỉnh: Trong bài này, một cây mà mỗi đỉnh không phải lá đều có đỉnh con trái và đỉnh con phải, đồng thời tất cả các đỉnh lá có cùng độ sâu, được gọi là cây nhị phân hoàn hảo. Đánh số các đỉnh của cây nhị phân hoàn hảo theo thứ tự từ trên xuống dưới, từ trái sang phải; cây tạo bởi một số đỉnh có số hiệu nhỏ nhất được gọi là cây nhị phân hoàn chỉnh.