Muchii Permutate

Se dă un arbore cu $N$ noduri (numerotate de la $1$ la $N$) și considerăm muchiile sale numerotate de la $1$ la $N - 1$ (în ordinea în care sunt date în input). Un arbore este un graf neorientat, conex și aciclic.

Fie $P$ o permutare a numerelor de la $1$ la $N - 1$. Pentru această permutare $P$ dată, atribuim fiecărei muchii de index $i$ o pondere egală cu $P[i]$. Apoi, considerăm un algoritm în care inițial nu avem nicio muchie în arbore și începem să le adăugăm una cate una, în ordinea numerotării lor (practic în ordinea în care sunt date în input, de la $1$ la $N - 1$ - ordinea de adăugare nu depinde de ponderi).

Pentru ca permutarea $P$ să fie considerată validă, la fiecare pas din algoritm se cere ca orice componentă conexă maximală (cu cel puțin $2$ noduri) formată până acum să aibă doar muchii cu ponderi consecutive - aici componentele sunt considerate individual (și doar cele maximale), deci toate trebuie să respecte condiția, la orice pas al algoritmului.

Cerință

Dându-se numărul $N$, reprezentând numărul de noduri din arbore, respectiv cele $N - 1$ muchii ale arborelui (în ordinea din enunț), să se determine numărul minim de inversiuni dintr-o permutare validă, precum și numărul de permutări valide care ating acest minim (modulo $10^9 + 7$).

Detalii de implementare

Concurenții vor avea de implementat o singură funcție:

std::pair<long long, int> solve(int N, std::vector<int> U, std::vector<int> V);

care primește ca parametri:

• $N$, numărul de noduri din arbore
• Șirurile $U$ și $V$, unde perechea $U[i], V[i]$ reprezintă capetele muchiei $i + 1$ din arbore (după numerotarea din enunț), pentru $i$ de la $0$ la $N - 2$.

Funcția solve va fi apelată o singură dată.

Restricții

• $2 \leq N \leq 500 \ 000$
• $1 \leq U_i, V_i \leq N$, pentru $0 \leq i \leq N - 2$
• Atenție: Doar numărul de permutări valide care au un număr minim de inversiuni se calculează modulo $10^9 + 7$. Pentru numărul minim de inversiuni se calculează valoarea exactă.

Exemplul 1

input

7
3 7
2 5
2 6
1 3
1 2
2 4

stdout

2 2

Explicație

Pentru primul exemplu, cele două permutări valide optime care respectă constrângerile și obțin minimul de $2$ inversiuni sunt:

• $P = (1, 3, 4, 2, 5, 6)$
• $P = (3, 1, 2, 4, 5, 6)$

Exemplul 2

input

20
16 17
4 5
8 9
11 12
18 19
1 2
14 15
7 8
19 20
6 7
15 16
3 4
12 13
9 10
2 3
17 18
5 6
10 11
13 14

output

48 8

Explicație

Pentru al doilea exemplu, numărul minim de inversiuni al unei permutări valide este $48$ și există $8$ permutări valide cu acest număr minim de inversiuni.