Ученые в тайной химической лаборатории в Хорватии изучают химические связи в недавно обнаруженном веществе инопланетного происхождения. Имеющаяся в распоряжении ученых порция вещества состоит из N молекул, соединенных между собой N - 1 ковалентными связями, и все молекулы объединены этими связями (не обязательно напрямую) в единую сеть.
Так как вещество нестабильное, в каждой молекуле регулярно возникают импульсы, перемещающиеся по веществу через существующие связи в обоих направлениях. Ученые собираются стабилизировать вещество, направив ковалентные связи (то есть, дав импульсам возможность путешествовать по ним между молекулами лишь в одном направлении). Показатель нестабильности вещества определяется длиной максимального пути, который может пройти импульс в нем, и ученые хотят сделать эту величину как можно меньше.
Помогите ученым создать вещество с минимальным показателем нестабильности, указав необходимое направление ковалентных связей.
Первая строка содержит одно целое число N ( 2 ≤ N ≤ 100000 ). Каждая из последующих N - 1 строк содержит по два целых числа a i и b i ( 1 ≤ a i , b i ≤ N ), которые показывают что молекулы с номерами a i и b i соединены ковалентной связью.
Выведите N - 1 строку, каждая из которых должна содержать 1 если ковалентная связь должна быть направлена от a i к b i или 0 в противном случае.
Решения, в которых N ≤ 20 , будут оцениваться в 30 баллов.
3 1 2 2 3
0 1
4 2 1 1 3 4 1
1 0 1
На родной планете Чубакки растет очень большое дерево, на ветках которого вуки строят свои домики. Чубакке стало интересно, как быстро можно попасть из некоторых домиков в другие. Вам придется ответить на несколько его вопросов, чтобы он вас отпустил.
Вам дано дерево с N вершинами порядка K , то есть каждая вершина дерева может иметь не более K потомков. Дерево создано по принципу "минимальной энергии": вершины в нем располагается на новом уровне только тогда, когда все места на предыдущем уровне (слева направо) заняты. В таком же порядке вершины дерева пронумерованы, начиная с 1.
Вам необходимо ответить на Q запросов вида " x y ", где ответом является расстояние (количество ребер в минимальном пути) в данном дереве между вершинами с номерами x и y .
Первая строка содержит три целых числа: N ( 1 ≤ N ≤ 10 15 ), K ( 1 ≤ K ≤ 1000 ) и Q ( 1 ≤ Q ≤ 100000 ). Каждая из следующих Q строк содержит пару чисел x y ( 1 ≤ x , y ≤ N , x ≠ y ) - запросы, описанные в условии.
Выведите Q строк, в каждой из которых одно целое число - ответ на соответствующий запрос.
Решения, работающие при 1 ≤ N , Q ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие при 1 ≤ N , Q ≤ 100000 , будут оцениваться в 50 баллов.
7 2 3 1 2 2 1 4 7
1 1 4
9 3 3 8 9 5 7 8 4
2 2 3
Давным-давно в одной далекой-далекой галактике, было N планет. Также было N - 1 межпланетных магистралей, соединявших между собой все планеты (не обязательно напрямую). Иными словами, сеть планет и магистралей образовывала дерево. Кроме того, каждая магистраль имеет свой показатель интересности, заданный неотрицательным целым числом. Пара планет ( A , B ) называется скучной, если выполняются следующие условия:
1. A и B - различные планеты.
2. В действующей сети межпланетных магистралей существует путь между A и B .
3. Побитовый XOR показателей интересности всех магистралей в этом пути равен 0.
Ныне в галактике правит злой император, и он планирует использовать Силу, чтобы уничтожить все межпланетные магистрали в определенном порядке. Для того, чтобы спасти вселенную от гибели, вам необходимо определить количество пар скучных планет и после каждого разрушения вновь подсчитывать эту величину.
Первая строка содержит одно целое число N ( 1 ≤ N ≤ 100000 ). Каждая из следующих N - 1 строк содержит три целых числа A i , B i , Z i ( 1 ≤ A i , B i ≤ 100000 , 0 ≤ Z i ≤ 1000000000 ), которые означают, что планеты с номерами A i и B i соединены магистралью с показателем интересности Z i . Последняя строка содержит N - 1 число: перестановку натуральных чисел от 1 до N - 1 , отражающую порядок уничтожения магистралей (если i -е число в строке равно j , то император уничтожит дорогу между планетами A j и B j на i -м шаге).
Выведите N строк, в k -й строке выведите одно число - количество пар скучных планет после уничтожения k - 1 дорог.
Решения, работающие при N ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие в случае когда показатель интересности всех путей равен 0, будут оцениваться не менее чем в 30 баллов.
2 1 2 0 1
1 0
3 1 2 4 2 3 4 1 2
1 0 0
4 1 2 0 2 3 0 2 4 0 3 1 2
6 3 1 0
Дан ориентированный граф. Подсчитайте, сколько пар вершин ( i , j ) имеют общего предка. Общим предком вершин i и j называется такая вершину k , что и i , и j достижимы из k .
В первой строке входного файла содержатся целые числа 1 ≤ N ≤ 10 4 , 0 ≤ M ≤ 10 4 — количество вершин и рёбер в графе. Далее следуют M строк по два числа от 1 до N . Пара чисел ( a , b ) означает, что из вершины a есть ребро в вершину b .
Выведите одно целое число — количество пар.
2 1 1 2
4
3 2 2 1 3 1
7
Как гласят старые малоярославские легенды, где-то далеко-далеко, где сборная России когда-то готовилась к международной олимпиаде, в одной из общеобразовательных школ живёт Граф. Ориентированность Графа, как следует из легенд, меняется от дня ко дню вместе с количеством вершин и ребер, что позволяет Графине и её отражению не скучать и играть во множество игр на Графе.
Вот уже многие дни Граф обрёл постоянную ориентированность; однако в последнее время Граф часто стал бывать раздражительным и колючим, и для Графини настали нелёгкие дни. Чтобы хоть как-то облегчить себе жизнь, Графиня решила написать программу, которая по текущему состоянию, то есть набору вершин и рёбер, сообщит Графине, является ли граф колючим. По опыту прошлых дней, Графиня заключила, что Граф является колючим, если и только если через любое его ребро проходит не более чем один простой цикл.
Напомним, что последовательность ребер ( u 1 , u 2 ) , ( u 2 , u 3 ) , ..., ( u k - 1 , u k ) , ( u k , u 1 ) является простым циклом, если вершины u 1 , u 2 , ..., u k попарно различны. Простой цикл проходит через ребро e , если ребро e содержится в последовательности ребер цикла.
Петлёй в графе называется ребро ( u , v ) , т.ч. u = v .
Рёбра ( u 1 , v 1 ) и ( u 2 , v 2 ) называются кратными, если u 1 = u 2 и v 1 = v 2 .
Помогите Графине понять, является ли её Граф, являющийся ориентированным графом без петель и кратных ребер, колючим или нет.
В первой строке записаны целые неотрицательные числа n и m ( 1 ≤ n ≤ 500 000 , 0 ≤ m ≤ 10 6 - количество вершин и рёбер графа-Графа.
Далее в следующих m строках записано по паре целых чисел u , v , 1 ≤ u , v ≤ n , u ≠ v .
Гарантируется, что в Графе не существует петель и кратных ребер.
Выведите слово " YES ", если Граф является колючим, и " NO " иначе.
3 3 1 2 2 3 3 1
YES
3 4 1 2 2 3 3 1 1 3
NO