Сегодня Игорь и Ира вместе с друзьями — Сашей и Лешей — решили поиграть в новую настольную игру «Brass Birmingham».
В каждом раунде игроки делают ходы по очереди. Во время хода игрок может построить производство в городах, дорогу, соединяющую два города, либо выполнить действие.
В свой ход Игорь хочет открыть как можно больше своих заводов. Для того, чтобы открыть один завод, игроку требуется перенести к заводу ровно один бочонок «пива», ведь без бочонка «пива» не получится торжественно открыть предприятие. Таким образом, чем больше бочонков «пива» Игорь подвезёт, тем больше заводов он сможет открыть.
Бочонки «пива» располагаются на пивоварнях, ранее построенных игроками. На каждой пивоварне располагается ровно один бочонок «пива».
Для открытия заводов Игорь хочет использовать свои бочонки «пива», которые он заготовил ранее. Если их окажется недостаточно, то Игорю придется использовать бочонки «пива» других игроков.
Правила игры гласят, что бочонки «пива» со своих пивоварен можно использовать без ограничений. Если же игрок хочет перенести бочонок «пива» с чужой пивоварни для построения своего завода, то данное действие можно сделать, только если завод и пивоварня находятся в одном городе, либо между пивоварней и заводом существует путь по дорогам.
Какое количество своих и чужих бочонков «пива» использует Игорь?
В первой строке записано целое число $$$N$$$ $$$(2\leq N\leq 10^5)$$$ — количество городов в игре.
Во второй строке записано целое число $$$M$$$ $$$(1\leq M\leq 10^5)$$$ — количество заводов, которые хочет открыть Игорь.
В третьей строке записано $$$M$$$ целых чисел $$$m_i$$$ $$$(1\leq m_i\leq N)$$$ — города, в которых Игорь хочет открыть заводы. В одном городе может быть несколько заводов.
В четвертой строке записано целое число $$$K$$$ $$$(1\leq K\leq 10^5)$$$ — количество пивоварен Игоря.
В пятой строке записано $$$K$$$ целых чисел $$$k_i$$$ $$$(1\leq k_i\leq N)$$$ — города, в которых располагаются пивоварни Игоря. В одном городе может быть несколько пивоварен Игоря.
В шестой строке записано целое число $$$L$$$ $$$(1\leq L\leq 10^5)$$$ — количество пивоварен других игроков.
В седьмой строке записано $$$L$$$ целых чисел $$$l_i$$$ $$$(1\leq l_i\leq N)$$$ — города, в которых располагаются пивоварни других игроков. В одном городе может быть несколько пивоварен других игроков.
В восьмой строке записано целое число $$$G$$$ $$$(1\leq G\leq 10^5)$$$ — количество уже построенных дорог.
В следующих $$$G$$$ строках записаны пары целых чисел $$$a_i, b_i$$$ $$$(1\leq a_i,b_i\leq N)$$$ — города, которые соединяются дорогой с номером $$$i$$$.
В единственной строке выведите два целых числа, разделенных пробелом: количество своих и количество чужих бочонков «пива», которое потребуются Игорю.
8 4 1 4 3 2 2 2 8 4 8 7 6 5 4 1 2 2 3 4 3 4 5
2 1
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
2 3
