{"problem":{"name":"C. Фабрика","description":{"content":"В Межзвездном Космоаналитическом Бюро очень удивились, узнав, что сообщение от космоаналитика на Сарке получено не было. Более того, самого космоаналитика нигде не могли найти... Не могли найти в тече","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10220C"},"statements":[{"statement_type":"Markdown","content":"В Межзвездном Космоаналитическом Бюро очень удивились, узнав, что сообщение от космоаналитика на Сарке получено не было. Более того, самого космоаналитика нигде не могли найти... Не могли найти в течении целого года.\n\nЧерез несколько недель на Флорине, неподалеку одной из кыртовых фабрик Валлона Марч нашла человека, потерявшего память. Его подвергли психозондированию, уничтожив часть его воспоминаний и спрятав остальные в глубинах сознания. Управляющий фабрикой, резидент Мирлин Теренс, разрешил Валлоне взять найденыша себе на попечение, добился для нее дополнительного пайка и талонов на одежду — сделал все, чтобы двое взрослых (из них один незарегистрированный) могли прожить на жалованье одного. Валлону такое положение вполне устраивало: красавицей она не была, поэтому пока остальные девушки нянчили собственных детей, Валлона занималась Риком — так назвали умалишенного (и поверьте, забот с ним поначалу было не меньше).\n\nЧерез некоторое время к Рику начала постепенно возвращаться память, и пусть он ничего не помнил о своем прошлом, он уже работал на фабрике. И вот сегодня утром по дороге на свое рабочее место Рик столкнулся с Валлоной. Столкнулся в прямом смысле этого слова, потому что людей на фабрике было много, и все куда-то ужасно спешили, что сильно затрудняло перемещение. Фабрика представляет собой $n$ помещений, соединенных $n -1$ двусторонними коридорами таким образом, чтобы между любыми двумя помещениями существовал ровно один путь. Рик подумал: а что если утром сделать движение по всем коридорам односторонним, чтобы избежать подобных столкновений? Идея может и неплохая, но при этом из некоторых помещений нельзя будет добраться в удаленные части фабрики. А самому Рику, Валлоне, да и остальным рабочим надо было попасть в определенные места. Рику известно про $m$ человек, что с утра они должны дойти из помещения $s_i$ в помещение $f_i$, поэтому коридоры на их пути надо ориентировать таким образом, чтобы возможность перемещения из начала пути $s_i$ в конец $f_i$ не пропадала.\n\nСознание Рика еще не до конца прояснилось, поэтому он просит вас узнать, можно ли ориентировать все коридоры требуемым способом?\n\nПервая строка содержит два числа $n$ и $m$ — количество помещений на фабрике и количество знакомых Рика $(1 <= n, m <= 2 dot.op 10^5)$.\n\nВ следующих $n -1$ строке заданы номера пар помещений $u_i, v_i$, соединенных коридорами $(1 <= u_i, v_i <= n)$. Гарантируется, что из каждого помещения фабрики можно добраться до каждого.\n\nСледующие $m$ строк содержат числа $s_i$ и $f_i$ — начальные и конечные вершины путей, возможность перемещения по которым должна сохраниться.\n\nЕсли ориентировать коридоры описанным образом невозможно, выведите \"NO\" (без кавычек). В противном случае в первой строке выведите \"YES\" (без кавычек), а в следующих $n -1$ строках — описание всех коридоров в любом порядке. Для каждого коридора выведите номера двух помещений, которые он соединяет, таким образом, чтобы из первого можно было перемещаться во второе.\n\nРассмотрим второй пример. Опишем пути всех знакомых Рика после того, как коридоры были проориентированы.\n\n$6 arrow.r 2 arrow.r 1 arrow.r 3 arrow.r 10$\n\n$13 arrow.r 11 arrow.r 4 arrow.r 1$\n\n$5 arrow.r 1 arrow.r 3 arrow.r 9 arrow.r 12 arrow.r 14$\n\n$15 arrow.r 12$\n\n$2 arrow.r 8$\n\n## Входные Данные\n\nПервая строка содержит два числа $n$ и $m$ — количество помещений на фабрике и количество знакомых Рика $(1 <= n, m <= 2 dot.op 10^5)$.В следующих $n -1$ строке заданы номера пар помещений $u_i, v_i$, соединенных коридорами $(1 <= u_i, v_i <= n)$. Гарантируется, что из каждого помещения фабрики можно добраться до каждого.Следующие $m$ строк содержат числа $s_i$ и $f_i$ — начальные и конечные вершины путей, возможность перемещения по которым должна сохраниться.\n\n## Выходные Данные\n\nЕсли ориентировать коридоры описанным образом невозможно, выведите \"NO\" (без кавычек). В противном случае в первой строке выведите \"YES\" (без кавычек), а в следующих $n -1$ строках — описание всех коридоров в любом порядке. Для каждого коридора выведите номера двух помещений, которые он соединяет, таким образом, чтобы из первого можно было перемещаться во второе.\n\n## Примеры\n\nВходные данные5 5\n2 1\n4 1\n5 3\n3 4\n1 2\n5 3\n5 4\n1 4\n3 4\nВыходные данныеYES\n1 2\n1 4\n3 4\n5 3\nВходные данные15 5\n1 2\n1 3\n1 4\n1 5\n2 6\n2 7\n2 8\n3 9\n3 10\n4 11\n9 12\n11 13\n12 14\n12 15\n6 10\n13 1\n5 14\n15 12\n2 8\nВыходные данныеYES\n2 1\n6 2\n7 2\n2 8\n1 3\n3 9\n9 12\n12 14\n15 12\n3 10\n4 1\n11 4\n13 11\n5 1\nВходные данные5 5\n1 3\n5 1\n4 2\n3 4\n4 3\n4 3\n3 2\n1 2\n5 4\nВыходные данныеNO\n\n## Примечание\n\nРассмотрим второй пример. Опишем пути всех знакомых Рика после того, как коридоры были проориентированы.$6 arrow.r 2 arrow.r 1 arrow.r 3 arrow.r 10$$13 arrow.r 11 arrow.r 4 arrow.r 1$$5 arrow.r 1 arrow.r 3 arrow.r 9 arrow.r 12 arrow.r 14$$15 arrow.r 12$$2 arrow.r 8$\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ S = \\{P_1, P_2, \\dots, P_n\\} \\subset \\mathbb{Z}^2 $ be a finite set of distinct points in the 2D integer lattice, where $ P_i = (x_i, y_i) $.  \nThe **Voronoi region** of point $ P_i $ is defined as:  \n$$\nR_i = \\left\\{ K \\in \\mathbb{R}^2 \\mid \\forall j \\in \\{1, \\dots, n\\}, \\; d(P_i, K) \\leq d(P_j, K) \\right\\}\n$$  \nwhere $ d(P_i, K) = |x_i - k_x| + |y_i - k_y| $ is the Manhattan distance.\n\nA region $ R_i $ is **unbounded** if for every $ R > 0 $, there exists a point $ K \\in R_i $ such that $ \\|K\\|_2 > R $ (i.e., it extends arbitrarily far from the origin).\n\n**Constraints**  \n1. $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 100 $  \n2. For all $ i \\in \\{1, \\dots, n\\} $, $ x_i, y_i \\in \\mathbb{Z} $, $ |x_i|, |y_i| \\leq 10^4 $\n\n**Objective**  \nCompute the number of unbounded regions in the Manhattan-distance Voronoi diagram of $ S $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10220C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}