{"raw_statement":[{"iden":"statement","content":"У Рудольфа есть любимая собачка, которую зовут Байер. Как и всякий ответственный хозяин, Рудольф старается воспитывать своего питомца и учит его выполнять различные команды. Однако традиционные трюки вроде «_Сидеть_» и «_Апорт_» не очень-то и впечатляют Рудольфа, поэтому он придумал для Байера кое-что получше. Рудольф — большой фанат структур данных, в связи с чем он предлагает Байеру рисовать красно-чёрные деревья.\n\nКрасно-чёрное дерево — это древовидная структура данных, имеющая следующие особенности: \n\nСегодня Рудольф решил пообедать в своём любимом кафе. К сожалению, туда не пускают с животными, поэтому Байеру придётся остаться дома. Чтобы питомцу не было грустно, Рудольф поручил ему составить примеры красно-чёрных деревьев. Байер с радостью согласился и с энтузиазмом взялся за работу.\n\nЧерез три часа Рудольф вернулся из кафе сытый и довольный. К своему удивлению, он обнаружил, что Байер успел нарисовать огромное количество красно-чёрных деревьев: среди них были маленькие, средние, большие и даже очень большие. Рудольф смог визуально оценить только деревья небольшого размера и нашёл несколько ошибок. А вот проверить остальные деревья оказалось очень сложно, поэтому Рудольф попросил вас автоматизировать оценку трудов Байера.\n\nПервая строка содержит число n (1 ≤ n ≤ 105) — количество внутренних узлов красно-чёрного дерева. \n\nСледующие n строк описывают внутренние узлы. Каждая из них содержит строку ci, целое число ki и целое число pi (, 1 ≤ ki, pi ≤ 1018) — цвет узла, ключ узла и ключ родителя, соответственно. Для корневого узла pi =  - 1.\n\nГарантируется, что описанный во входных данных граф является деревом и имеет корень.\n\nВыведите «_YES_» (без кавычек), если входные данные содержат корректное описание красно-чёрного дерева (с учётом добавления листовых узлов). В противном случае выведите «_NO_» (без кавычек).\n\n"},{"iden":"входные данные","content":"Первая строка содержит число n (1 ≤ n ≤ 105) — количество внутренних узлов красно-чёрного дерева. Следующие n строк описывают внутренние узлы. Каждая из них содержит строку ci, целое число ki и целое число pi (, 1 ≤ ki, pi ≤ 1018) — цвет узла, ключ узла и ключ родителя, соответственно. Для корневого узла pi =  - 1.Гарантируется, что описанный во входных данных граф является деревом и имеет корень."},{"iden":"выходные данные","content":"Выведите «_YES_» (без кавычек), если входные данные содержат корректное описание красно-чёрного дерева (с учётом добавления листовых узлов). В противном случае выведите «_NO_» (без кавычек)."},{"iden":"примеры","content":"Входные данные5red 30 40black 20 -1black 10 20black 40 20red 50 40Выходные данныеYESВходные данные5red 3 4red 5 4black 2 -1black 1 2red 4 2Выходные данныеNO"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of internal nodes.  \nLet $ V = \\{v_1, \\dots, v_n\\} $ be the set of internal nodes, where each node $ v_i $ is characterized by:  \n- $ c_i \\in \\{\\text{red}, \\text{black}\\} $: color of the node,  \n- $ k_i \\in \\mathbb{Z} $: key of the node,  \n- $ p_i \\in \\mathbb{Z} \\cup \\{-1\\} $: key of the parent node ($ p_i = -1 $ iff $ v_i $ is root).  \n\nLet $ T $ be the tree structure induced by parent-child relationships. Add external (leaf) nodes (black, key-less) as children where needed to satisfy red-black tree properties.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq k_i, p_i \\leq 10^{18} $ for all $ i $, and $ p_i = -1 $ for exactly one node (the root).  \n3. The graph is a tree with unique root.  \n4. All keys are distinct.\n\n**Objective**  \nDetermine whether $ T $, with added black leaf nodes, satisfies all red-black tree properties:  \n\n1. Every node is either red or black.  \n2. The root is black.  \n3. Every leaf (external node) is black.  \n4. If a node is red, then both its children are black.  \n5. For each node, all simple paths from it to descendant leaves contain the same number of black nodes (black-height).  \n\nOutput \"YES\" if all properties hold; otherwise, output \"NO\".","simple_statement":"You are given a description of a red-black tree with n internal nodes. Each node has a color (red or black), a key, and a parent key. The root has parent -1.\n\nCheck if this description forms a valid red-black tree by verifying:\n\n1. Every node is either red or black.\n2. The root is black.\n3. Every red node has only black children.\n4. All paths from the root to any leaf have the same number of black nodes.\n5. All leaves (null children) are black.\n\nOutput \"YES\" if valid, \"NO\" otherwise.","has_page_source":false}