Equivalence Classes in Labeled Trees by Leaf Counts

We are given the following definitions. For a tree ( T(V,E) ) and a subset ( S\subseteq V ), let [ f(S, T)=|{ v\in S : \deg_{T[S]}(v)\le 1}|, ] where ( T[S] ) denotes the subgraph induced by ( S ) (i.e. keeping only those edges whose both endpoints are in ( S )).

For two trees ( T_1(V,E_1) ) and ( T_2(V,E_2) ) on the same vertex set ( V ), we say [ T_1 \preceq T_2 \quad\text{if and only if}\quad \forall S_2\subseteq V,; \exists S_1;\mbox{with}; S_2\subseteq S_1\subseteq V ;\mbox{such that}; f(S_1,T_1)\le f(S_2,T_2). ] Two trees are defined to be equivalent, written ( T_1 \sim T_2 ), if ( T_1 \preceq T_2 ) and ( T_2 \preceq T_1 ). It turns out that for labeled trees on ( n ) vertices the equivalence relation is completely determined by the number of leaves (i.e. the number of vertices of degree ( \le 1 ) in the whole tree). In other words, for any two trees ( T_1 ) and ( T_2 ) on ( n\ge 2 ) vertices, ( T_1\sim T_2 ) if and only if they have the same number of leaves.

We are given ( k ) labeled trees ( T_1,T_2,\dots,T_k ) on ( n ) vertices. Answer the following two questions (all answers modulo (998,244,353)):

1. Count the number of equivalence classes of labeled trees ( T ) satisfying ( T\preceq T_i ) for every ( 1\le i\le k ). Since equivalence is determined by the number of leaves and every tree on ( n\ge 2 ) vertices has at least 2 leaves, the condition ( T \preceq T_i ) forces [ \ell(T)\le \ell(T_i)\quad \text{for every } i, \quad\text{so } \ell(T)\le L_{\min}, ] where ( L_{\min}=\min_{1\le i\le k}\ell(T_i) ). Thus, the answer is the count of possible leaf counts, which is ( \max(0, L_{\min}-1) ) (and when ( n=1 ) the unique tree forms a single equivalence class).

2. Count the number of labeled trees ( T ) satisfying ( T_i\preceq T ) for every ( 1\le i\le k ). Again, taking ( S_2=V ) we deduce that ( \ell(T_i)\le \ell(T) ) for every ( i ). Let ( L_{\max}=\max_{1\le i\le k}\ell(T_i) ); then ( T ) must have at least ( L_{\max} ) leaves. When ( n\ge 2 ) the number of labeled trees on ( n ) vertices is ( n^{n-2} ) (by Cayley’s formula) and one may show (for ( n\ge3 )) that the number of trees with exactly ( \ell ) leaves is given by [ \displaystyle N(n,\ell)= {n\choose \ell} \cdot \frac{(n-2)!}{(\ell-1)!,(n-\ell-1)!}, \quad 2\le \ell\le n-1. ] For ( n=2 ) the unique tree has 2 leaves. Hence the answer to (2) is [ \sum_{\ell= L_{\max}}^{n-1}N(n,\ell)\quad (\text{with the convention that when } n=1 \text{ the answer is }1 ). ]

Note that the counting objects in (1) and (2) are different. It is guaranteed that after taking modulo (998,244,353) both answers are nonzero.

Input Format:

• The first line contains two integers \( n \) and \( k \) (with \( n\ge1 \) and \( k\ge1 \)).
• This is followed by \( k\times (n-1) \) lines. For each tree, there are exactly \( n-1 \) lines, each containing two integers \( u \) and \( v \) representing an edge between vertices \( u \) and \( v \) (vertices are labeled from 1 to \( n \)).

Output Format:

• Output two integers separated by a space: the answer to question (1) and the answer to question (2), both taken modulo \(998\,244\,353\).

inputFormat

The first line contains two integers n and k.

Then for each of the k trees, there are n-1 lines, each with two integers u and v (1-based indices) that describe an edge of the tree.

outputFormat

Output two space‐separated integers: the answer to (1) (the number of equivalence classes among trees T satisfying T &preceq T_i for all i) and the answer to (2) (the number of trees T satisfying T_i &preceq T for all i), both modulo 998244353.

sample

3 1
1 2
2 3

1 3