Bat Virus

Neverland is a country with N cities (indexed from 0 to N-1). The cities are connected to each other by a network of R two-way roads.

Two cities are considered to be neighbors if they’re directly connected by a two-way road.

To an unfortunate turn of events, the country got struck by a mysterious bat virus. Initially (on day D₁), patients with the virus were reported from some cities in the country. The virus spreads in a weird, but interesting way.

Consider a city C₀ , with C₁ , C₂ , C₃ , C₄ , …, C_t neighbor cities. On day D_i , let’s say there are P₀ , P₁ , P₂ , P₃ , P₄ , …, P_t patients corresponding to each city. Then number of patients in C₀ on day \(D_{(i+1)} = max( C_0, \frac{C_1}{2}, \frac{C_2}{2}, \frac{C_3}{2}, \frac{C_4}{2}, ..., \frac{C_t}{2})\)

Given the road network and initial conditions of virus, your task is to find the maximum number of bat-virus patients that will be recorded in the country (P_max), and the number of days (D_max) it will take for P_max to appear first.

Input Format

First line contains two space seperated integers N and R. (Number of Cities, and the number of two-way roads)
R lines follow, with i ^th line having two space seperated integers S_i and E_i , the index of two cities connected by the road R_i .
Next line contains a single integer M, the initial number of cities where the virus appeared.
M lines follow, with j ^th of them having two space seperated integers C_j and P_j , the index of the city, and the number of patients reported respectively.

Output Format

Two integers, D_max and P_max

Constraints

• 1 \(\leq\) N \(\leq\) 2*10⁴
• 1 \(\leq\) R \(\leq\) 5*10⁴
• 1 \(\leq\) M \(\leq\) 5*10³
• 0 \(\leq\) S_i, E_i, C_j \(\leq\) N-1
• 0 \(\leq\) P_j \(\leq\) 3*10⁷
• 0 \(\leq\) i \(\leq\) R
• 0 \(\leq\) j \(\leq\) M
• S_i \(\neq\) E_i
• A single city can be connected to 1 city at minimum and N-1 cities at maximum.
• There are no isolated cities.

Limits

• Time Limit: 1s
• Memory Limit: 256MB

Sample Input 0

6 5
0 1
1 2
2 3
3 4
4 5
2
0 100
4 5

Sample Output 0

6 196