{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYankovich trabaja como ingeniero de software en una empresa llamada POI (Party Online Infinitely), como su nombre sugiere, es una empresa que promueve fiestas en línea. Para probar los sistemas, algunos empleados organizaron fiestas e invitaron solo a los empleados de la empresa con algunas restricciones.\u003c/p\u003e\u003cp\u003eLos empleados de la empresa forman una estructura jerárquica, donde cada uno tiene un gerente directo (excepto el dueño de la empresa) y no hay relaciones cíclicas. Debido a los procesos de promoción de la empresa, la edad de un empleado no es mayor que la edad de su gerente directo.\u003c/p\u003e\u003cp\u003eEstas fiestas iniciales funcionan de la siguiente manera: \u003c/p\u003e\u003cul\u003e \u003cli\u003e Cada fiesta $$$j$$$ tiene un dueño $$$O_j$$$ y un rango de edad, desde $$$L_j$$$ hasta $$$R_j$$$ . \u003c/li\u003e\u003cli\u003e Para ser invitado a una fiesta, un empleado necesita tener una edad dentro del rango de edad $$$[L_j, R_j]$$$ de la fiesta. Se garantiza que la edad del dueño de cada fiesta está dentro del rango de edad de sus fiestas. \u003c/li\u003e\u003cli\u003e Además de la restricción de edad, para ser invitado a una fiesta, un empleado debe trabajar directamente con otro empleado que será invitado (como gerente directo o subordinado directo), excepto para el dueño de la fiesta. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eYankovich es responsable de la aplicación que calcula datos sobre las fiestas en las que un usuario ha participado. Como tarea inicial, tiene que calcular cuántas fiestas fue invitado un empleado. Dado que llega tarde para entregar su primera tarea, ayúdalo a calcular esta información para estas fiestas iniciales.\u003c/p\u003e"}},{"title":"Entrada","value":{"format":"HTML","content":"\u003cp\u003eEn la primera línea hay dos enteros $$$N, M$$$ $$$(1 \\le N, M \\le 10^5)$$$ que representan el número de empleados y el número de fiestas iniciales, respectivamente.\u003c/p\u003e\u003cp\u003eLas siguientes $$$N$$$ líneas contienen los datos de los empleados. En la $$$i$$$-ésima de estas líneas hay dos enteros $$$A_i, B_i$$$ $$$(1 \\le A_i ≤ 10^5, 1 \\le B_i \\le N)$$$ que representan la edad del $$$i$$$-ésimo empleado y su gerente directo (los empleados están numerados del 1 al $$$N$$$, el dueño de la empresa es el número 1 y es el único empleado que tiene $$$B_i \u003d i$$$). Se garantiza que $$$A_i \\le A_{B_i}$$$.\u003c/p\u003e\u003cp\u003eLas siguientes $$$M$$$ líneas definen las fiestas iniciales. En la $$$j$$$-ésima de estas líneas hay tres enteros $$$O_j, L_j, R_j$$$ $$$(1 \\le L_j \\le A_{O_j} \\le R_j \\le 10^5)$$$ que representan el dueño de esta fiesta y su rango de edad.\u003c/p\u003e"}},{"title":"Salida","value":{"format":"HTML","content":"\u003cp\u003eImprime una sola línea que contenga $$$N$$$ enteros (separados por un solo espacio). El $$$i$$$-ésimo de estos números debería ser el número de fiestas a las que el empleado número $$$i$$$ fue invitado.\u003c/p\u003e"}},{"title":"Ejemplo 1","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\u003e10 3\n8 1\n3 5\n5 1\n2 3\n4 1\n3 3\n1 2\n7 1\n2 2\n3 2\n3 5 9\n5 3 8\n3 2 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 3 1 1 2 0 2 0 1 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}