G. Brass Birmingham: beer
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Today Igor and Ira with friends  — Sasha and Lesha — decided to play a new board game "Brass Birmingham".

In each round, the players take turns making moves. During the turn, the player can build one industry per city, a road connecting two cities, or perform an action.

In his turn, Igor wants to open as many of his factories as possible. To open one factory, the player needs to transfer exactly one barrel of "beer" to the factory, because without a barrel of "beer" it will not be possible to have a formal opening. Thus, the more barrels of "beer" Igor transfers, the more factories he will be able to open.

Barrels of "beer" are in breweries previously built by players. Each brewery has exactly one barrel of "beer".

Igor wants to use his barrels of "beer", which he has prepared earlier, to open factories. If they are not enough, then Igor will have to use the barrels of other players.

The rules of the game state that one can use barrels of "beer" from his breweries without any restrictions. If the player wants to move a barrel of "beer" from someone else's brewery to build his factory, then this action can be done only if the factory and the brewery are in the same city, or there is a road path between the brewery and the factory.

How many of his own and other people's barrels of "beer" will Igor use?

Input

The first string contains an integer $$$N$$$ $$$(2\leq N\leq 10^5)$$$ — the number of cities in the game.

The second string contains an integer $$$M$$$ $$$(1\leq M\leq 10^5)$$$ — the number of factories Igor wants to open.

The third string contains $$$M$$$ integers $$$m_i$$$ $$$(1\leq m_i\leq N)$$$ — cities where Igor wants to open factories. There may be several factories in one city.

The fourth string contains an integer $$$K$$$ $$$(1\leq K\leq 10^5)$$$ — the number of Igor's breweries.

The fifth string contains $$$K$$$ integers $$$k_i$$$ $$$(1\leq k_i\leq N)$$$ — the cities where Igor's breweries are located. There may be several Igor's breweries in one city.

The sixth string contains an integer $$$L$$$ $$$(1\leq L\leq 10^5)$$$ — the number of breweries of other players.

The seventh string contains $$$L$$$ integers $$$l_i$$$ $$$(1\leq l_i\leq N)$$$ — cities where breweries of other players are located. There may be several breweries of other players in one city.

The eighth string contains an integer $$$G$$$ $$$(1\leq G\leq 10^5)$$$ — the number of already built roads.

The following $$$G$$$ strings contain pairs of integers $$$a_i, b_i$$$ $$$(1\leq a_i,b_i\leq N)$$$ — cities that are connected by a road number $$$i$$$.

Output

In a single string print two integers separated by a space: the number of his own and the number of other people's barrels of "beer" that Igor will need.

Examples
Input
8
4
1 4 3 2
2
2 8
4
8 7 6 5
4
1 2
2 3
4 3
4 5
Output
2 1
Input
6
5
2 3 5 2 5
2
1 2
8
2 2 1 6 4 1 2 3
9
4 3
5 2
4 6
1 2
5 6
6 5
1 2
3 4
6 1
Output
2 3