{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe map of Bertown can be represented as a set of $$$n$$$ intersections, numbered from $$$1$$$ to $$$n$$$ and connected by $$$m$$$ one-way roads. It is possible to move along the roads from any intersection to any other intersection. The length of some path from one intersection to another is the number of roads that one has to traverse along the path. The shortest path from one intersection $$$v$$$ to another intersection $$$u$$$ is the path that starts in $$$v$$$, ends in $$$u$$$ and has the minimum length among all such paths.\u003c/p\u003e\u003cp\u003ePolycarp lives near the intersection $$$s$$$ and works in a building near the intersection $$$t$$$. Every day he gets from $$$s$$$ to $$$t$$$ by car. Today he has chosen the following path to his workplace: $$$p_1$$$, $$$p_2$$$, ..., $$$p_k$$$, where $$$p_1 \u003d s$$$, $$$p_k \u003d t$$$, and all other elements of this sequence are the intermediate intersections, listed in the order Polycarp arrived at them. Polycarp never arrived at the same intersection twice, so all elements of this sequence are pairwise distinct. \u003cspan class\u003d\"tex-font-style-bf\"\u003eNote that you know Polycarp\u0027s path beforehand (it is fixed), and it is not necessarily one of the shortest paths from $$$s$$$ to $$$t$$$\u003c/span\u003e.\u003c/p\u003e\u003cp\u003ePolycarp\u0027s car has a complex navigation system installed in it. Let\u0027s describe how it works. When Polycarp starts his journey at the intersection $$$s$$$, the system chooses some shortest path from $$$s$$$ to $$$t$$$ and shows it to Polycarp. Let\u0027s denote the next intersection in the chosen path as $$$v$$$. If Polycarp chooses to drive along the road from $$$s$$$ to $$$v$$$, then the navigator shows him the same shortest path (obviously, starting from $$$v$$$ as soon as he arrives at this intersection). However, if Polycarp chooses to drive to another intersection $$$w$$$ instead, the navigator \u003cspan class\u003d\"tex-font-style-bf\"\u003erebuilds\u003c/span\u003e the path: as soon as Polycarp arrives at $$$w$$$, the navigation system chooses some shortest path from $$$w$$$ to $$$t$$$ and shows it to Polycarp. The same process continues until Polycarp arrives at $$$t$$$: if Polycarp moves along the road recommended by the system, it maintains the shortest path it has already built; but if Polycarp chooses some other path, the system \u003cspan class\u003d\"tex-font-style-bf\"\u003erebuilds\u003c/span\u003e the path by the same rules.\u003c/p\u003e\u003cp\u003eHere is an example. Suppose the map of Bertown looks as follows, and Polycarp drives along the path $$$[1, 2, 3, 4]$$$ ($$$s \u003d 1$$$, $$$t \u003d 4$$$): \u003c/p\u003e\u003ccenter\u003e\u003cp\u003eCheck the picture by the link \u003ca href\u003d\"https://tk.codeforces.com/a.png\"\u003ehttp://tk.codeforces.com/a.png\u003c/a\u003e\u003c/p\u003e\u003c/center\u003e \u003col\u003e \u003cli\u003e When Polycarp starts at $$$1$$$, the system chooses some shortest path from $$$1$$$ to $$$4$$$. There is only one such path, it is $$$[1, 5, 4]$$$; \u003c/li\u003e\u003cli\u003e Polycarp chooses to drive to $$$2$$$, which is not along the path chosen by the system. When Polycarp arrives at $$$2$$$, the navigator \u003cspan class\u003d\"tex-font-style-bf\"\u003erebuilds\u003c/span\u003e the path by choosing some shortest path from $$$2$$$ to $$$4$$$, for example, $$$[2, 6, 4]$$$ (note that it could choose $$$[2, 3, 4]$$$); \u003c/li\u003e\u003cli\u003e Polycarp chooses to drive to $$$3$$$, which is not along the path chosen by the system. When Polycarp arrives at $$$3$$$, the navigator \u003cspan class\u003d\"tex-font-style-bf\"\u003erebuilds\u003c/span\u003e the path by choosing the only shortest path from $$$3$$$ to $$$4$$$, which is $$$[3, 4]$$$; \u003c/li\u003e\u003cli\u003e Polycarp arrives at $$$4$$$ along the road chosen by the navigator, so the system does not have to rebuild anything. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eOverall, we get $$$2$$$ rebuilds in this scenario. Note that if the system chose $$$[2, 3, 4]$$$ instead of $$$[2, 6, 4]$$$ during the second step, there would be only $$$1$$$ rebuild (since Polycarp goes along the path, so the system maintains the path $$$[3, 4]$$$ during the third step).\u003c/p\u003e\u003cp\u003eThe example shows us that the number of rebuilds can differ even if the map of Bertown and the path chosen by Polycarp stays the same. Given this information (the map and Polycarp\u0027s path), can you determine the minimum and the maximum number of rebuilds that could have happened during the journey?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \\le n \\le m \\le 2 \\cdot 10^5$$$) — the number of intersections and one-way roads in Bertown, respectively.\u003c/p\u003e\u003cp\u003eThen $$$m$$$ lines follow, each describing a road. Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \\le u, v \\le n$$$, $$$u \\ne v$$$) denoting a road from intersection $$$u$$$ to intersection $$$v$$$. All roads in Bertown are pairwise distinct, which means that each ordered pair $$$(u, v)$$$ appears at most once in these $$$m$$$ lines (but if there is a road $$$(u, v)$$$, the road $$$(v, u)$$$ can also appear).\u003c/p\u003e\u003cp\u003eThe following line contains one integer $$$k$$$ ($$$2 \\le k \\le n$$$) — the number of intersections in Polycarp\u0027s path from home to his workplace.\u003c/p\u003e\u003cp\u003eThe last line contains $$$k$$$ integers $$$p_1$$$, $$$p_2$$$, ..., $$$p_k$$$ ($$$1 \\le p_i \\le n$$$, all these integers are pairwise distinct) — the intersections along Polycarp\u0027s path in the order he arrived at them. $$$p_1$$$ is the intersection where Polycarp lives ($$$s \u003d p_1$$$), and $$$p_k$$$ is the intersection where Polycarp\u0027s workplace is situated ($$$t \u003d p_k$$$). It is guaranteed that for every $$$i \\in [1, k - 1]$$$ the road from $$$p_i$$$ to $$$p_{i + 1}$$$ exists, so the path goes along the roads of Bertown. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint two integers: the minimum and the maximum number of \u003cspan class\u003d\"tex-font-style-bf\"\u003erebuilds\u003c/span\u003e that could have happened during the journey.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 9\n1 5\n5 4\n1 2\n2 3\n3 4\n4 1\n2 6\n6 4\n4 2\n4\n1 2 3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 7\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 1\n7\n1 2 3 4 5 6 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e8 13\n8 7\n8 6\n7 5\n7 4\n6 5\n6 4\n5 3\n5 2\n4 3\n4 2\n3 1\n2 1\n1 8\n5\n8 7 5 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}