树和森林
题号:NC52488
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

有一片森林,森林中有m颗树,每棵树大小都是n且结构都一模一样,由题目给出,现在你有m - 1次操作,每次操作将第a颗树的u号点和第b颗树的v号点连接(保证他们之前是不连通的),求m次操作后整颗树所有点对距离和,答案对998244353取模

输入描述:

第一行两个正整数n,m(1≤n,m≤1000)

接下来n−1行,每行两个正整数u,v(1≤u,v≤n),表示初始时每棵树的边

接下来m−1行,每行四个正整数a,b,u,v(1 <= a, b <= m, 1 <= u, v <= n)

输出描述:

输出一个数表示答案
示例1

输入

复制
3 2
1 2
2 3
1 2 1 1

输出

复制
35