{"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\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eSoteros\u003c/span\u003e is the biggest organized crime syndicate of Soteropolis. They are feared and respected. Members of \u003cspan class\u003d\"tex-font-style-it\"\u003eSoteros\u003c/span\u003e follow a very rigid hierarchy. Sotero, the big boss, is the direct boss of some members, which in turn are direct boss of other members, and so on, like in a rooted tree structure. Therefore, Sotero is indirectly boss of the whole organization.\u003c/p\u003e\u003cp\u003eWe can imagine a numbered rooted tree, where Sotero is represented by vertex $$$1$$$. The other $$$n - 1$$$ members are represented by numbers between $$$2$$$ and $$$n$$$. The direct boss of the $$$i$$$-th member is $$$p_i$$$. Notice that every one has \u003cspan class\u003d\"tex-font-style-bf\"\u003eexactly\u003c/span\u003e one direct boss, except for Sotero.\u003c/p\u003e\u003cp\u003eSoteropolis is a city with $$$K$$$ junctions and a bunch of two-way streets connecting pairs of these junctions. \u003cspan class\u003d\"tex-font-style-it\"\u003eSoteros\u003c/span\u003e members have the culture of making themselves present on the streets. This is also true for the big boss Sotero. Every member of the organization is responsible for conducting business in \u003cspan class\u003d\"tex-font-style-bf\"\u003eat most\u003c/span\u003e one street of Soteropolis. More specifically, if the $$$i$$$-th member is responsible for some street, then junctions connected by this street are $$$u_i, v_i$$$.\u003c/p\u003e\u003cp\u003ePolo is an undercover agent working for SIA (Soteropolis Intelligence Agency) which finally got the chance to choose which member of \u003cspan class\u003d\"tex-font-style-it\"\u003eSoteros\u003c/span\u003e he wants to work for. If he chooses to work for member $$$i$$$, then he will have free pass through all the streets that members (directly or indirectly) leadered by $$$i$$$ are responsible for, but he won\u0027t be able to traverse \u003cspan class\u003d\"tex-font-style-it\"\u003eany\u003c/span\u003e other streets of the town.\u003c/p\u003e\u003cp\u003ePolo definitely want to keep a low profile, but he won\u0027t be able to do much if he can\u0027t move around the city. He asked you to make an analysis to help on his decision. \u003c/p\u003e\u003cp\u003eA connected region of Soteropolis is a maximal set of junctions such that for every pair of these junctions there is a path between them consisting only of streets Polo can freely traverse. In particular, an isolated junction (with no streets Polo can traverse around it) is a connected region.\u003c/p\u003e\u003cp\u003eFor each member of \u003cspan class\u003d\"tex-font-style-it\"\u003eSoteros\u003c/span\u003e, you should compute the number of connected regions Polo will be able to traverse if he chooses to work for such member.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n, K$$$ ($$$2 \\leq n, K \\leq 10^5$$$) – the number of members of \u003cspan class\u003d\"tex-font-style-it\"\u003eSoteros\u003c/span\u003e and the number of junctions of Soteropolis, respectively.\u003c/p\u003e\u003cp\u003eThe second line contains $$$n - 1$$$ integers separated by spaces. The $$$i$$$-th of them is $$$p_{i+1}$$$ ($$$1 \\leq p_{i+1} \\leq i$$$) – the direct boss of the $$$(i + 1)$$$-th member.\u003c/p\u003e\u003cp\u003eThe next $$$n$$$ lines contains two integers each. If the $$$i$$$-th of these lines contains \u003cspan class\u003d\"tex-font-style-tt\"\u003e0 0\u003c/span\u003e, then the $$$i$$$-th member is responsible for no street. Otherwise, it contains two integers $$$u_i, v_i$$$ ($$$1 \\leq u_i, v_i \\leq K$$$; $$$u_i \\neq v_i$$$) – the streets which the $$$i$$$-th member is responsible for.\u003c/p\u003e\u003cp\u003eTwo distinct members can be responsible for a street connecting the same pair of junctions $$$u_i, v_i$$$. That means they are responsible for the same street.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput $$$n$$$ lines. The $$$i$$$-th of them should contain an integer – the number of connected regions Polo will be able to traverse if he chooses to work for member $$$i$$$.\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\u003e3 3\n1 2\n0 0\n1 2\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1\n2\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 7\n1 1 1 2 2 5 5\n1 2\n2 3\n0 0\n6 7\n2 7\n7 5\n7 3\n5 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n4\n7\n6\n4\n6\n6\n6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}