{"trustable":false,"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":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003e\n Новый год прошёл, но Resha решил не убирать ёлку, а немного переукрасить её. К нему пришли его друзья Kerim и Gural, чтобы помочь переукрасить ёлку.\n \u003c/p\u003e\n \u003cp\u003e\n Ёлка представляет собой обычное неориентированное дерево из\n \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e вершин с корнем в вершине\n \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e.\n \u003c/p\u003e\n \u003cp\u003eВам требуется обрабатывать запросы двух типов:\u003c/p\u003e\n \u003col\u003e\n \u003cli\u003e\n Перекрасить все вершины из поддерева вершины\n \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e в цвет\n \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\n \u003e.\n \u003c/li\u003e\n \u003cli\u003e\n Найти количество различных цветов в поддереве вершины\n \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\n \u003e.\n \u003c/li\u003e\n \u003c/ol\u003e"}},{"title":"Входные данные","value":{"format":"HTML","content":" \u003cp\u003e\n В первой строке находится пара целых чисел\n \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003em\u003c/i\u003e ≤ 4·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\n \u003e) — количество вершин в дереве и количество запросов.\n \u003c/p\u003e\n \u003cp\u003e\n Во второй строке находятся\n \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e целых чисел\n \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\n \u003e\n (\u003cspan class\u003d\"tex-span\"\n \u003e1 ≤ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 60\u003c/span\n \u003e) — цвет \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\n \u003e-й вершины.\n \u003c/p\u003e\n \u003cp\u003e\n В каждой из следующих \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e строк находится пара целых чисел\n \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\n \u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\n \u003e\n (\u003cspan class\u003d\"tex-span\"\n \u003e1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\n \u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\n \u003e) — вершины, которые соединяет \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\n \u003e-е ребро дерева. Гарантируется, что вам задано корректное\n неориентированное дерево.\n \u003c/p\u003e\n \u003cp\u003e\n В последних \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e строках находятся описания запросов. Каждое описание начинается с целого цисла\n \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003c/span\n \u003e\n (\u003cspan class\u003d\"tex-span\"\n \u003e1 ≤ \u003ci\u003et\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e ≤ 2\u003c/span\n \u003e) — типа запроса. Для запросов первого типа далее следует пара целых\n чисел\n \u003cspan class\u003d\"tex-span\"\n \u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\n \u003e, \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003c/span\n \u003e\n (\u003cspan class\u003d\"tex-span\"\n \u003e1 ≤ \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e, 1 ≤\n \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e ≤ 60\u003c/span\n \u003e) — номер вершины дерева в поддереве которой все вершины\n перекрашиваются в цвет\n \u003cspan class\u003d\"tex-span\"\n \u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003c/span\n \u003e. Для запросов второго типа далее следует целое число\n \u003cspan class\u003d\"tex-span\"\n \u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003c/span\n \u003e\n (\u003cspan class\u003d\"tex-span\"\n \u003e1 ≤ \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e ≤\n \u003ci\u003en\u003c/i\u003e\u003c/span\n \u003e) — номер вершины в поддереве которой нужно посчитать количество\n различных цветов.\n \u003c/p\u003e"}},{"title":"Выходные данные","value":{"format":"HTML","content":" \u003cp\u003e\n Для каждого запроса второго типа выведите одно целое число\n \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e — количество различных цветов в поддереве вершины, заданной в запросе.\n \u003c/p\u003e\n \u003cp\u003e\n Числа нужно выводить в отдельных строках, в порядке появления запросов во входных данных.\n \u003c/p\u003e\n "}},{"title":"Примеры","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e7 10\u003cbr\u003e1 1 1 1 1 1 1\u003cbr\u003e1 2\u003cbr\u003e1 3\u003cbr\u003e1 4\u003cbr\u003e3 5\u003cbr\u003e3 6\u003cbr\u003e3 7\u003cbr\u003e1 3 2\u003cbr\u003e2 1\u003cbr\u003e1 4 3\u003cbr\u003e2 1\u003cbr\u003e1 2 5\u003cbr\u003e2 1\u003cbr\u003e1 6 4\u003cbr\u003e2 1\u003cbr\u003e2 2\u003cbr\u003e2 3\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e2\u003cbr\u003e3\u003cbr\u003e4\u003cbr\u003e5\u003cbr\u003e1\u003cbr\u003e2\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e23 30\u003cbr\u003e1 2 2 6 5 3 2 1 1 1 2 4 5 3 4 4 3 3 3 3 3 4 6\u003cbr\u003e1 2\u003cbr\u003e1 3\u003cbr\u003e1 4\u003cbr\u003e2 5\u003cbr\u003e2 6\u003cbr\u003e3 7\u003cbr\u003e3 8\u003cbr\u003e4 9\u003cbr\u003e4 10\u003cbr\u003e4 11\u003cbr\u003e6 12\u003cbr\u003e6 13\u003cbr\u003e7 14\u003cbr\u003e7 15\u003cbr\u003e7 16\u003cbr\u003e8 17\u003cbr\u003e8 18\u003cbr\u003e10 19\u003cbr\u003e10 20\u003cbr\u003e10 21\u003cbr\u003e11 22\u003cbr\u003e11 23\u003cbr\u003e2 1\u003cbr\u003e2 5\u003cbr\u003e2 6\u003cbr\u003e2 7\u003cbr\u003e2 8\u003cbr\u003e2 9\u003cbr\u003e2 10\u003cbr\u003e2 11\u003cbr\u003e2 4\u003cbr\u003e1 12 1\u003cbr\u003e1 13 1\u003cbr\u003e1 14 1\u003cbr\u003e1 15 1\u003cbr\u003e1 16 1\u003cbr\u003e1 17 1\u003cbr\u003e1 18 1\u003cbr\u003e1 19 1\u003cbr\u003e1 20 1\u003cbr\u003e1 21 1\u003cbr\u003e1 22 1\u003cbr\u003e1 23 1\u003cbr\u003e2 1\u003cbr\u003e2 5\u003cbr\u003e2 6\u003cbr\u003e2 7\u003cbr\u003e2 8\u003cbr\u003e2 9\u003cbr\u003e2 10\u003cbr\u003e2 11\u003cbr\u003e2 4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e6\u003cbr\u003e1\u003cbr\u003e3\u003cbr\u003e3\u003cbr\u003e2\u003cbr\u003e1\u003cbr\u003e2\u003cbr\u003e3\u003cbr\u003e5\u003cbr\u003e5\u003cbr\u003e1\u003cbr\u003e2\u003cbr\u003e2\u003cbr\u003e1\u003cbr\u003e1\u003cbr\u003e1\u003cbr\u003e2\u003cbr\u003e3\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}