Tree Intersection Labeling

This problem contains three sub‐problems. You are given two trees (each a connected acyclic graph) on n vertices with vertex labels from 1 to n. One tree is called the red tree and the other the blue tree. You have an integer parameter y. You want to assign each vertex an integer from 1 to y such that for any two vertices p and q, if there exists a path (a₁=p, a₂, …, a_m=q) that is a path in both trees then the labels assigned to p and q must be equal. (A path exists in a tree if every consecutive pair of vertices in the sequence is connected by an edge in that tree.)

It is not hard to see that the condition forces all vertices in a connected component of the graph G defined by the common edges (i.e. those edges that appear in both trees) to receive the same number. In other words, if the common edges decompose the set of vertices into c connected components then a valid labeling is obtained by assigning an arbitrary number in [1, y] to each component. Hence, for a fixed pair of trees the number of valid labelings is

$$y^{c}\ \ \ (\mbox{\(c\) is the number of connected components of } G). $$

However, the problem asks you to answer one of the following three queries (our input contains a parameter op which is 0, 1, or 2):

1. Problem 0: Two trees (the red tree and the blue tree) are given. Compute the number of valid labelings modulo 998244353.
2. Problem 1: The blue tree is given. For each of the n^n-2 possible red trees (all trees on n nodes), compute the answer for Problem 0 and output the sum of these answers modulo 998244353.
3. Problem 2: For each of the n^n-2 possible blue trees, consider all n^n-2 possible red trees and let the answer be as in Problem 1. Compute the sum of the answers over all blue trees modulo 998244353.

Input format explanation:

• The first line contains three integers: op (0, 1, or 2), n, and y.
• If op = 0, the next n-1 lines describe the red tree. Each line contains two integers u and v meaning that there is an edge between vertices u and v. This is followed by another n-1 lines describing the blue tree in the same format.
• If op = 1, the next n-1 lines describe the blue tree.
• If op = 2, no additional tree is given.

Output:

Output a single integer – the answer to the corresponding problem modulo 998244353.

Note: A tree on n labeled nodes has exactly n^n-2 different forms (Cayley’s formula).

inputFormat

The input begins with a line containing three integers op (0, 1 or 2), n and y (1 ≤ y), where n is the number of nodes in each tree.

• If op = 0:
  • The next n-1 lines each contain two integers u v representing an edge in the red tree.
  • The following n-1 lines each contain two integers u v representing an edge in the blue tree.
• If op = 1:
  • The next n-1 lines describe the blue tree.
• If op = 2:
  • No additional lines are provided.

outputFormat

Output a single integer representing the answer to the designated problem modulo 998244353.

sample

0 3 2
1 2
2 3
1 2
2 3

2