Codeforces Round 722 (Div. 1)


A. Parsa's Humongous Tree
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
2
1 6
3 8
1 2
3
1 3
4 6
7 9
1 2
2 3
6
3 14
12 20
12 19
2 12
10 17
3 17
3 2
6 5
1 5
2 6
4 6
Output
7
8
62
----------------------------------------------------------------------------------------------------
B. Kavi on Pairing Duty
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
1
Output
1
Input
2
Output
3
Input
3
Output
6
Input
100
Output
688750769
----------------------------------------------------------------------------------------------------
C. Trees of Tranquillity
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
4
1 2 3
1 2 3
5
1 2 3 4
1 1 1 1
6
1 1 1 1 2
1 2 1 2 2
7
1 1 3 4 4 5
1 2 1 4 2 5
Output
1
4
1
3
----------------------------------------------------------------------------------------------------
D. It's a bird! No, it's a plane! No, it's AaParsa!
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 4
0 1 1
0 2 3
1 0 1
2 0 1
Output
0 1 2 
1 0 2 
1 2 0 
Input
6 6
0 0 1
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
Output
0 2 3 3 4 4 
4 0 2 3 3 4 
4 4 0 2 3 3 
3 4 4 0 2 3 
3 3 4 4 0 2 
2 3 3 4 4 0 
Input
4 5
0 1 1
1 3 2
2 2 10
3 0 1
0 0 2
Output
0 1 2 3 
3 0 3 2 
12 13 0 11 
1 2 2 0 
----------------------------------------------------------------------------------------------------
E. Mashtali and Hagh Trees
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
1
Output
5
Input
2
Output
31
Input
344031
Output
272040628
----------------------------------------------------------------------------------------------------
F. AmShZ Farm
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
1 1
Output
1
Input
2 2
Output
8
Input
5 4
Output
50400
Input
20 100
Output
807645526
Input
10000000 10000
Output
883232350
----------------------------------------------------------------------------------------------------
