Задача A. Электричество ≡

Условие

В одной сельской школе решили начать преподавание информатики. Начали с создания кабинета информатики. Так как специального помещения для этих целей в школе нет, то было решено переоборудовать кабинет математики.

Было закуплено n устройств: системные блоки, мониторы, проектор и т. д. Однако, когда начался процесс подключения, неожиданно выяснилось, что в кабинете есть только одна электрическая розетка.

Решение было найдено достаточно быстро — были куплены k сетевых фильтров. После этого выяснилось, что как устройства, так и сетевые фильтры обладают различными характеристиками — это делает процесс подключения нетривиальным. Для каждого сетевого фильтра известно число A_i розеток в нем и максимальная суммарная мощность B_i устройств, которые могут быть в него подключены, а для каждого устройства известна потребляемая им мощность C_i.

Теперь необходимо составить схему подключения устройств с использованием сетевых фильтров такую, что суммарная мощность устройств, включенных в каждый сетевой фильтр (как напрямую, так и через другие сетевые фильтры) не превосходит соответствующего значения B_i, а число устройств и других сетевых фильтров, напрямую включенных в этот, не превосходит A_i. При этом, в соответствии с правилами пожарной безопасности, в каждый сетевой фильтр можно подключать не более одного другого сетевого фильтра.

Можно считать, что единственная в классе розетка рассчитана на достаточно большую мощность — она выдержит подключение всех имеющихся устройств. Отметим также, что при необходимости в розетку можно включить не сетевой фильтр, а устройство напрямую.

Напишите программу, которая найдет требуемую схему подключения устройств.

Формат входного файла

Первая строка входного файла содержит k — число имеющихся в наличии сетевых фильтров. Далее следуют k строк, описывающих эти сетевые фильтры: каждая из них содержит по два целых числа: A_i и B_i — количество розеток в нем и максимальную суммарную мощность приборов, которые можно включить в него, соответственно.

Следующая строка содержит n — число приборов, которые нужно подключить. Последняя строка входного файла содержит мощности этих приборов: C₁, …, C_n.

Формат выходного файла

В выходной файл выведите слово Yes, если все приборы можно подключить с использованием имеющихся в наличии сетевых фильтров, и слово No — в противном случае.

Если ответ на задачу положительный, то далее выведите описание схемы подключения. Оно должно состоять из двух строк. Первая из этих строк должна описывать подключение сетевых фильтров: для каждого из них выведите номер фильтра, в который он подключен~(если он подключен в единственную розетку в классе, то выведите число 0, а если он вообще не используется, то число −1). Вторая из этих строк должна описывать подключение приборов: для каждого из приборов выведите номер сетевого фильтра~(если прибор следует подключить непосредственно в розетку, то выведите число 0), в который он подключен.

Учитывайте, что в каждый сетевой фильтр может быть подключен не более чем один другой сетевой фильтр, а подключать фильтр сам к себе не разрешается. Если в сетевой фильтр не включены (напрямую или через другие сетевые фильтры) никакие устройства, то он также не должен быть никуда включен. Кроме этого, если фильтр не включен~(напрямую или через другие сетевые фильтры) в розетку, то он также не должен быть никуда включен.

Сетевые фильтры нумеруются, начиная с единицы, в порядке их перечисления во входном файле. Порядок вывода описания подключения фильтров и приборов должен совпадать с порядком их перечисления во входном файле.

Ограничения

1 ≤ k ≤ 10⁵;

2 ≤ A_i ≤ 10⁵;

1 ≤ B_i ≤ 10⁹;

1 ≤ n ≤ 10⁵;

1 ≤ C_i ≤ 10⁹;

Примеры тестов

2
2 20
2 10
3
10 5 5

Yes
0 1 
1 2 2

1
2 10
1
20

Yes
-1
0

Задача B. Пробежки по Манхэттену ≡

Условие

Дороги Нью-Манхэттена устроены следующим образом. С юга на север через каждые сто метров проходит авеню, с запада на восток через каждые сто метров проходит улица. Авеню и улицы нумеруются целыми числами. Меньшие номера соответствуют западным авеню и южным улицам. Таким образом, можно построить прямоугольную систему координат так, чтобы точка (x, y) лежала на пересечении x-ой авеню и y-ой улицы. Легко заметить, что для того, чтобы в Нью-Манхэттене дойти от точки (x₁, y₁) до точки (x₂, y₂) нужно пройти |x₂ − x₁| + |y₂ − y₁| кварталов. Эта величина называется манхэттенским расстоянием между точками (x₁, y₁) и (x₂, y₂).

Миша живет в Нью-Манхэттене и каждое утро делает пробежку по городу. Он выбегает из своего дома, который находится в точке (0, 0) и бежит по случайному маршруту. Каждую минуту Миша либо остается на том же перекрестке, что и минуту назад, или перемещается на один квартал в любом направлении. Чтобы не заблудиться Миша берет с собой навигатор, который каждые t минут говорит Мише, в какой точке он находится. К сожалению, навигатор показывает не точное положение Миши, он может показать любую из точек, манхэттенское расстояние от которых до Миши не превышает d.

Через t⋅ n минут от начала пробежки, получив n-е сообщение от навигатора, Миша решил, что пора бежать домой. Для этого он хочет понять, в каких точках он может находиться. Помогите Мише сделать это.

Формат входного файла

Первая строка входного файла содержит числа t, d и n.

Далее n строк описывают данные, полученные от навигатора. Строка номер i содержит числа x_i и y_i — данные, полученные от навигатора через t ⋅ i минут от начала пробежки.

Формат выходного файла

В первой строке выходного файла выведите число m — число точек, в которых может находиться Миша. Далее выведите m пар чисел — координаты точек. Точки можно вывести в произвольном порядке.

Гарантируется, что навигатор исправен и что существует по крайней мере одна точка, в которой может находиться Миша.

Ограничения

1≤ t≤ 100;

1≤ d≤ 100;

1≤ n≤ 100;

Примеры тестов

2 1 5
0 1
-2 1
-2 3
0 3
2 5

2
1 5
2 4

Задача C. Обход в глубину ≡

Условие

Недавно на кружке по программированию Петя узнал об обходе в глубину. Обход в глубину используется во многих алгоритмах на графах. Петя сразу же реализовал обход в глубину на своих любимых языках программирования — паскале и си.

var
  a: array [1..maxn, 1..maxn] 
       of boolean;
  visited: array [1..maxn] 
       of boolean;

procedure dfs(v: integer);
var 
  i: integer;
begin
  writeln(v);
  visited[v] := true;
  for i := 1 to n do begin
    if a[v][i] and 
        not visited[i] then 
    begin
      dfs(i);
      writeln(v);
    end;
  end;
end;

procedure graph_dfs;
var
  i: integer;
begin
  for i := 1 to n do
    if not visited[i] then
    	dfs(i);
end;

int a[maxn + 1][maxn + 1];
int visited[maxn + 1];

void dfs(int v) {
  printf("%d\n", v);
  visited[v] = 1;
  for (int i = 1; i <= n; i++) {
    if ((a[v][i] != 0) && 
        (visited[i] == 0)) {
      dfs(i);
      printf("%d\n", v);
    }
  }
}

void graph_dfs() {
  for (int i = 1; i <= n; i++) {
    if (visited[i] == 0) {
      dfs(i);
    }
  }
}

Петина программа хранит граф с использованием матрицы смежности в массиве "a" (вершины графа пронумерованы от 1 до n). В массиве "visited" помечается, в каких вершинах обход в глубину уже побывал.

Петя запустил процедуру "graph_dfs" для некоторого неориентированного графа G с n вершинами и сохранил ее вывод. А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество ребер могло быть в графе G. Помогите ему выяснить это!

Формат входного файла

Формат выходного файла

Ограничения

1 ≤ n ≤ 300

1 ≤ l ≤ 2 n−1

Примеры тестов

6 10
1
2
3
2
4
2
1
5
6
5

6
1 2
1 3
1 4
2 3
2 4
5 6