\documentclass[a4paper,oneside,fleqn,11pt,russian]{extarticle}
\usepackage[cp1251]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage{amssymb,amsmath}
%\usepackage{pscyr}
\usepackage{graphicx} 
%****************************************************************************************
\textheight=26.8cm
\textwidth=17cm
\oddsidemargin=-0.5cm
\topmargin=-3.0cm
\headsep = 6pt
\voffset=1.2cm
\allowdisplaybreaks
\DeclareGraphicsExtensions {.png}
%****************************************************************************************
\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent\textbf{Олимпиада <<Ломоносов>> по информатике. 2024-2025 учебный год}

\noindent\textbf{Заключительный этап. 11 класс}

\noindent\textbf{Задачи, ответы, критерии}

\vspace{6pt}\noindent\textbf{Задача 1. Незнайка и Коллатц}

\vspace{6pt}\noindent\textbf{Критерий оценивания решений задачи 1}

\noindent
Общим критерием оценивания решения любой задачи является количество тестов, верно пройденных программой, составленной участником. Сначала решение проверяется на тестах из условия. Если не пройден хотя бы один из них, то решение оценивается в $0$ технических баллов. Если тесты из условия пройдены, то решение проверяется на основном наборе тестов. Высчитывается доля (в процентах) верно пройденных тестов из основного набора по отношению к общему количеству тестов в наборе. Полученное количество процентов, округлённое до целого, определяет количество технических баллов за решение.

\vspace{6pt}\noindent\textbf{Технические баллы за задачу 1}

\noindent
За решение задачи начисляется от 0 до 100 технических баллов по критерию, указанному выше. 

\vspace{6pt}\noindent\textbf{Перевод технических баллов в оценку}

\noindent
По каждой задаче определяются самые удачные её решения, отправленные участником. Технические баллы за них суммируются. Полученная сумма умножается на корректировочный коэффициент $\frac{10}{35}$ и округляется до целого. Результат определяет итоговую оценку.


\vspace{6pt}\noindent\textbf{Условия задачи 1}


\noindent
Незнайка очень полюбил функцию Коллатца $f(n) = \begin{cases} \frac{n}{2}, &n - \text{четное число} \\ 3n+1, & n - \text{нечетное число} \end{cases}$, про которую есть недоказанная гипотеза о том, что её применение снова и снова, стартуя с любого натурального ненулевого числа, всегда приводит к числу 1, после чего возникает цикл $1 \rightarrow 4 \rightarrow 2 \rightarrow 1$. Незнайке пришло в голову, что можно применять обратное преобразование, и от какого-то натурального ненулевого числа $a$ переходить к одному из чисел $b$, такому что $f(b)=a$. Он обозначил такое обратное преобразование $f^{-1}$ и стал искать способы перейти от стартового числа $n_1$ к финишному числу $n_2$ за минимально возможное количество шагов, применяя на каждом шаге либо функцию Коллатца $f$, либо обратное преобразование $f^{-1}$ к текущему результату, полученному на предыдущем шаге (на первом шаге за текущий результат Незнайка брал число $n_1$). Например, от $n_1=10$ к $n_2=21$ можно перейти за 5 шагов: $10 \rightarrow f(10)=5 \rightarrow f(5)=16 \rightarrow f^{-1}(16)=32 \rightarrow f^{-1}(32)=64 \rightarrow f^{-1}(64)=21$ 

\noindent
Полагая, что гипотеза Коллатца верна, помогите Незнайке написать программу, которая определяет минимально возможное количество шагов, за которые из данного стартового числа $n_1$ можно получить финишное число $n_2$. Пусть программа, если количество шагов не менее 2, выводит промежуточные числа, полученные на каждом шаге, кроме последнего.

\noindent
\textit{Формат ввода:} В первой строке вводится натуральное число $n_1$: $1 \leq n_1 \leq 10000$. Во второй строке содержится натуральное число $n_2$: $1 \leq n_2 \leq 10000$.

\noindent
\textit{Формат вывода:} В первой строке выводится либо наименьшее из возможных количество последовательных применений функции $f(x)$ или преобразования $f^{-1}(x)$, после которых стартовое число $n_1$ преобразуется в финишное число $n_2$, либо -1, если стартовое число $n_1$ не может быть преобразовано таким способом в финишное число $n_2$. Если $n_1=n_2$, то выводится 0. Если в первой строке было выведено число, большее 1, то во второй строке выводятся промежуточные результаты -- числа, полученные на каждом шаге, разделённые одиночным пробелом. В начале второй строки и в её конце пробел не ставится. Если в первой строке был выведен -1, 0 или 1, то вывод содержит лишь одну строку.\begin{verbatim}
Ввод примера №1:     Ввод примера №2:     Ввод примера №3:     Ввод примера №4:
10                   8                    10000                2
21                   1                    10000                1
Вывод примера №1:    Вывод примера №2:    Вывод примера №3:    Вывод примера №4:
5                    2                    0                    1
5 16 32 64           4
\end{verbatim}\noindent\textbf{Решение}

\noindent
Ставя каждому натуральному числу в соответствие вершину графа, и соединяя дугами все пары вершин с числами $a$ и $b$, такими что $f(a)=b$, мы получаем, так называемый, граф Коллатца. Из любой вершины этого графа можно двигаться только в сторону 1, путь до которой существует, если гипотеза Коллатца верна. Известно, что в диапазоне рассматриваемых чисел длина такого пути не превосходит 261. В этом можно убедиться с помощью предварительных расчётов. Длину 261 имеет путь от 6171 к 1. Находим путь к 1, ведущий из $n_1$. Находим путь к 1, ведущий из $n_2$. Находим вершину, находящуюся дальше всего от 1 и лежащую на обоих путях. Часть пути от $n_1$ до этой вершины, к которой в приписана задом наперёд часть пути от $n_2$ до этой вершины, образует ответ. Сама вершина, которую мы нашли, входит в ответ не более чем один раз. Её не следует включать в ответ, если она совпадает с $n_1$ и/или с $n_2$. При поиске пути к 1 следует иметь в виду, что $4 \rightarrow f^{-1}(4)=1$ и это короче, чем $4 \rightarrow f(4)=2 \rightarrow f(2)=1$. Другими словами, если $n_1$ и/или $n_2$ находятся в диапазоне от 1 до 2, то такие случаи надо анализировать отдельно. Также следует иметь в виду, что ради эффективности перед поиском путей можно проверить тривиальные случаи, когда $n_1$ и $n_2$ совпадают или находятся в одном шаге друг от друга.  Составляя программу, стоит иметь в виду, что промежуточные числа могут быть довольно велики. Так, на пути от 9663 к 1 лежит число 27114424.

\noindent\textbf{Код возможного решения}
\begin{verbatim}
program COLLATZ11(input, output);
const   PATH_LENGTH = 262;
type    massiv = array [1..PATH_LENGTH] of cardinal;
        path = record length : 0..PATH_LENGTH; numbers : massiv end;
function F(X : cardinal) : cardinal;
begin
      if (X mod 2) = 0 then F := X div 2 else F := 3 * X + 1
end;
procedure APPEND (V : cardinal; var P : PATH);
begin with P do begin
        length := length + 1;
        numbers[length] := V
      end
end;
procedure PATHTO1 (N : cardinal; var P : path);
begin
      P.length := 0;
      while N > 1 do begin
          APPEND(N, P);
          N := F(N);
      end;
        APPEND(1, P)
end;

var  N1, N2, V : cardinal;
     I, J, K, RESULT : cardinal;
     FLAG1, FLAG2 : boolean;
     P1, P2 : path;
begin FLAG1 := false;
      FLAG2 := false;
    readln(N1);
    read(N2);
    if N1=N2 then write(0) else begin
      if N1 > 1 then I := F(N1) else I := N1;
      if N2 > 1 then J := F(N2) else J := N2;
      if (I = N2) or (J = N1) or ((N1 = 4) and (N2 = 1)) or ((N1 = 1) and (N2 = 4)) then
        write(1)
      else begin
        PATHTO1(N1, P1);
        PATHTO1(N2, P2);
        I := P1.length;
        J := P2.length;
        while (I > 0) and (J > 0) and (P1.numbers[I] = P2.numbers[J]) do begin
          I := I - 1;
          J := J - 1;
        end;
        if (I >= 0) and (I < P1.length) then V := P1.numbers[I+1] else
        if (J >= 0) and (J < P2.length) then V := P2.numbers[J+1] else
        V := 1;
        RESULT := I + J;
        if ((N2 = 1) and (N1 > 2)) or ((N1 = 1) and (N2 > 2)) then begin
          RESULT := RESULT - 1;
          FLAG2 := true;
        end;
        writeln(RESULT);
        if I > 1 then begin
          write(P1.numbers[2]);
          for K := 3 to I do if not (FLAG2 and (P1.numbers[K] = 2)) then
           write(' ', P1.numbers[K]);
          FLAG1 := true
        end;
        if (V > 1) and (V <> N1) and (V <> N2) then
         if not (FLAG2 and (V = 2)) then begin
          if FLAG1 then write(' ');
          write(V);
          FLAG1 := true
         end;
        if J > 1 then begin
          if FLAG1 then if not (FLAG2 and (P2.numbers[J] = 2)) then write(' ');
          if not (FLAG2 and (P2.numbers[J] = 2)) then write(P2.numbers[J]);
          for K := J-1 downto 2 do begin
           if not (FLAG2 and (P2.numbers[K] <= 4)) then write(' ');
           if not (FLAG2 and (P2.numbers[K] = 2)) then write(P2.numbers[K])
          end;
        end
      end
    end
end.
\end{verbatim}
\newpage\noindent\textbf{Задача 2. Незнайка и недосортировка}

\vspace{6pt}\noindent\textbf{Критерий оценивания решений задачи 2}

\noindent
Общим критерием оценивания решения любой задачи является количество тестов, верно пройденных программой, составленной участником. Сначала решение проверяется на тестах из условия. Если не пройден хотя бы один из них, то решение оценивается в $0$ технических баллов. Если тесты из условия пройдены, то решение проверяется на основном наборе тестов. Высчитывается доля (в процентах) верно пройденных тестов из основного набора по отношению к общему количеству тестов в наборе. Полученное количество процентов, округлённое до целого, определяет количество технических баллов за решение.

\vspace{6pt}\noindent\textbf{Технические баллы за задачу 2}

\noindent
За решение задачи начисляется от 0 до 100 технических баллов по критерию, указанному выше. 

\vspace{6pt}\noindent\textbf{Перевод технических баллов в оценку}

\noindent
По каждой задаче определяются самые удачные её решения, отправленные участником. Технические баллы за них суммируются. Полученная сумма умножается на корректировочный коэффициент $\frac{10}{35}$ и округляется до целого. Результат определяет итоговую оценку.

\vspace{6pt}\noindent\textbf{Условия задачи 2}

\noindent
Знайка ввёл в Цветочном городе буквенную систему счисления. Это позиционная система счисления с основанием 52, в которой цифрами служат заглавные и строчные латинские буквы и только они. В ней используется такая таблица цифр и их значений:

\noindent
\setlength{\tabcolsep}{1.0pt}
\def\arraystretch{1.35}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} 
\hline
\small{цифра} & \,$A$\, & \,$B$\, & \,$C$\, & \,$D$\, & \,$E$\, & \,$F$\, & \,$G$\, & \,$H$\, & \,$I$\, & \,$J$\, & \,$K$\, & \,$L$\, & \,$M$\, & \,$N$\, & \,$O$\, & \,$P$\, & \,$Q$\, & \,$R$\, & \,$S$\, & \,$T$\, & \,$U$\, & \,$V$\, & \,$W$\, & \,$X$\, & \,$Y$\, & \,$Z$\, \\ \hline
\small{значение} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25\\ \hline \hline
\small{цифра} & \,$a$\, & \,$b$\, & \,$c$\, & \,$d$\, & \,$e$\, & \,$f$\, & \,$g$\, & \,$h$\, & \,$i$\, & \,$j$\, & \,$k$\, & \,$l$\, & \,$m$\, & \,$n$\, & \,$o$\, & \,$p$\, & \,$q$\, & \,$r$\, & \,$s$\, & \,$t$\, & \,$u$\, & \,$v$\, & \,$w$\, & \,$x$\, & \,$y$\, & \,$z$\, \\ \hline
\small{значение} & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 & 51\\ \hline
\end{tabular}

\noindent
\\
Приведем пример записи числа в буквенной системе счисления: $2025_{10}=38*52^{1}+49*52^{0}=mx$.

\noindent
Все стали пользоваться буквенной системой счисления, как положено, кроме Незнайки. Однажды Знайка заглянул в исписанный Незнайкой листок, схватился за голову и пришёл в ужас. В записи чисел помимо обычных латинских букв Незнайка задействовал как цифры буквы с крышками ($\widehat{A}\dots\widehat{Z}$ и $\widehat{a}\dots\widehat{z}$), буквы с волной ($\widetilde{A}\dots\widetilde{Z}$ и $\widetilde{a}\dots\widetilde{z}$) и буквы с нижними подчёркиваниями ($\underline{A}\dots\underline{Z}$ и $\underline{a}\dots\underline{z}$). Знайка обратился к Незнайке за разъяснениями. Выяснилось, что Незнайка модифицировал буквенную систему счисления, разрешив переполнять в ней разряды, т. е. записывать в них цифры со значениями, превышающими 51. При этом основание системы счисления он оставил прежним -- 52. Незнайка дополнил таблицу цифр и их значений:

\noindent
\setlength{\tabcolsep}{1.0pt}
\def\arraystretch{1.35}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} 
\hline
\small{цифра} & \,$\widehat{A}$\, & \,$\widehat{B}$\, & \,$\widehat{C}$\, & \,$\widehat{D}$\, & \,$\widehat{E}$\, & \,$\widehat{F}$\, & \,$\widehat{G}$\, & \,$\widehat{H}$\, & \,$\widehat{I}$\, & \,$\widehat{J}$\, & \,$\widehat{K}$\, & \,$\widehat{L}$\, & \,$\widehat{M}$\, & \,$\widehat{N}$\, & \,$\widehat{O}$\, & \,$\widehat{P}$\, & \,$\widehat{Q}$\, & \,$\widehat{R}$\, & \,$\widehat{S}$\, & \,$\widehat{T}$\, & \,$\widehat{U}$\, & \,$\widehat{V}$\, & \,$\widehat{W}$\, & \,$\widehat{X}$\, & \,$\widehat{Y}$\, & \,$\widehat{Z}$\, \\ \hline
\small{значение} & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 & 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 & 70 & 71 & 72 & 73 & 74 & 75 & 76 & 77\\ \hline
\hline
\small{цифра} & \,$\widehat{a}$\, & \,$\widehat{b}$\, & \,$\widehat{c}$\, & \,$\widehat{d}$\, & \,$\widehat{e}$\, & \,$\widehat{f}$\, & \,$\widehat{g}$\, & \,$\widehat{h}$\, & \,$\widehat{i}$\, & \,$\widehat{j}$\, & \,$\widehat{k}$\, & \,$\widehat{l}$\, & \,$\widehat{m}$\, & \,$\widehat{n}$\, & \,$\widehat{o}$\, & \,$\widehat{p}$\, & \,$\widehat{q}$\, & \,$\widehat{r}$\, & \,$\widehat{s}$\, & \,$\widehat{t}$\, & \,$\widehat{u}$\, & \,$\widehat{v}$\, & \,$\widehat{w}$\, & \,$\widehat{x}$\, & \,$\widehat{y}$\, & \,$\widehat{z}$\, \\ \hline
\small{значение} & 78 & 79 & 80 & 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & 89 & 90 & 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 & 101 & 102 & 103 \\ \hline
\hline
\small{цифра} & \,$\widetilde{A}$\, & \,$\widetilde{B}$\, & \,$\widetilde{C}$\, & \,$\widetilde{D}$\, & \,$\widetilde{E}$\, & \,$\widetilde{F}$\, & \,$\widetilde{G}$\, & \,$\widetilde{H}$\, & \,$\widetilde{I}$\, & \,$\widetilde{J}$\, & \,$\widetilde{K}$\, & \,$\widetilde{L}$\, & \,$\widetilde{M}$\, & \,$\widetilde{N}$\, & \,$\widetilde{O}$\, & \,$\widetilde{P}$\, & \,$\widetilde{Q}$\, & \,$\widetilde{R}$\, & \,$\widetilde{S}$\, & \,$\widetilde{T}$\, & \,$\widetilde{U}$\, & \,$\widetilde{V}$\, & \,$\widetilde{W}$\, & \,$\widetilde{X}$\, & \,$\widetilde{Y}$\, & \,$\widetilde{Z}$\, \\ \hline
\small{значение} & 104 & 105 & 106 & 107 & 108 & 109 & 110 & 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 & 121 & 122 & 123 & 124 & 125 & 126 & 127 & 128 & 129 \\ \hline
\hline
\small{цифра} & \,$\widetilde{a}$\, & \,$\widetilde{b}$\, & \,$\widetilde{c}$\, & \,$\widetilde{d}$\, & \,$\widetilde{e}$\, & \,$\widetilde{f}$\, & \,$\widetilde{g}$\, & \,$\widetilde{h}$\, & \,$\widetilde{i}$\, & \,$\widetilde{j}$\, & \,$\widetilde{k}$\, & \,$\widetilde{l}$\, & \,$\widetilde{m}$\, & \,$\widetilde{n}$\, & \,$\widetilde{o}$\, & \,$\widetilde{p}$\, & \,$\widetilde{q}$\, & \,$\widetilde{r}$\, & \,$\widetilde{s}$\, & \,$\widetilde{t}$\, & \,$\widetilde{u}$\, & \,$\widetilde{v}$\, & \,$\widetilde{w}$\, & \,$\widetilde{x}$\, & \,$\widetilde{y}$\, & \,$\widetilde{z}$\, \\ \hline
\small{значение} & 130 & 131 & 132 & 133 & 134 & 135 & 136 & 137 & 138 & 139 & 140 & 141 & 142 & 143 & 144 & 145 & 146 & 147 & 148 & 149 & 150 & 151 & 152 & 153 & 154 & 155 \\ \hline
\hline
\small{цифра} & \,$\underline{A}$\, & \,$\underline{B}$\, & \,$\underline{C}$\, & \,$\underline{D}$\, & \,$\underline{E}$\, & \,$\underline{F}$\, & \,$\underline{G}$\, & \,$\underline{H}$\, & \,$\underline{I}$\, & \,$\underline{J}$\, & \,$\underline{K}$\, & \,$\underline{L}$\, & \,$\underline{M}$\, & \,$\underline{N}$\, & \,$\underline{O}$\, & \,$\underline{P}$\, & \,$\underline{Q}$\, & \,$\underline{R}$\, & \,$\underline{S}$\, & \,$\underline{T}$\, & \,$\underline{U}$\, & \,$\underline{V}$\, & \,$\underline{W}$\, & \,$\underline{X}$\, & \,$\underline{Y}$\, & \,$\underline{Z}$\, \\ \hline
\small{значение} & 156 & 157 & 158 & 159 & 160 & 161 & 162 & 163 & 164 & 165 & 166 & 167 & 168 & 169 & 170 & 171 & 172 & 173 & 174 & 175 & 176 & 177 & 178 & 179 & 180 & 181 \\ \hline
\hline
\small{цифра} & \,$\underline{a}$\, & \,$\underline{b}$\, & \,$\underline{c}$\, & \,$\underline{d}$\, & \,$\underline{e}$\, & \,$\underline{f}$\, & \,$\underline{g}$\, & \,$\underline{h}$\, & \,$\underline{i}$\, & \,$\underline{j}$\, & \,$\underline{k}$\, & \,$\underline{l}$\, & \,$\underline{m}$\, & \,$\underline{n}$\, & \,$\underline{o}$\, & \,$\underline{p}$\, & \,$\underline{q}$\, & \,$\underline{r}$\, & \,$\underline{s}$\, & \,$\underline{t}$\, & \,$\underline{u}$\, & \,$\underline{v}$\, & \,$\underline{w}$\, & \,$\underline{x}$\, & \,$\underline{y}$\, & \,$\underline{z}$\, \\ \hline
\small{значение} & 182 & 183 & 184 & 185 & 186 & 187 & 188 & 189 & 190 & 191 & 192 & 193 & 194 & 195 & 196 & 197 & 198 & 199 & 200 & 201 & 202 & 203 & 204 & 205 & 206 & 207 \\ \hline
\end{tabular}

\noindent
\\
Знайка сразу понял, что модифицированная система позволяет одно и то же число записать по-разному. Например:\\
$2025_{10}=38*52^{1}+49*52^{0}=mx=37*52^{1}+101*52^{0}=l\widehat{x}=36*52^{1}+153*52^{0}=k\widetilde{x}=35*52^{1}+205*52^{0}=j\underline{x}$ 

\noindent
\\
Знайка решил доказать Незнайке его неправоту. Он предложил Незнайке отсортировать по убыванию последовательность различных чисел, записанных в модифицированной Незнайкой системе счисления. Знайка рассчитывал на то, что недостатки <<переполненной>> системы счисления станут очевидны сразу, как только понадобится выполнять сравнения чисел, записанных с её помощью. Но не тут-то было. Незнайка и бровью не повёл, и вскоре Знайка получил результат сортировки. Зная <<творческий>> подход Незнайки и заподозрив неладное, Знайка вгляделся в результат. И точно, сбылись его подозрения. Последовательность $A[i]$ оказалась недосортированной. В ней встретилась одна пара элементов $A[i_1]$ и $A[i_2]$ $(i_1 \neq i_2)$, стоящих не на своих местах. Последовательность оказалась бы убывающей лишь после обмена местами $A[i_1]$ и $A[i_2]$: установки прежнего числа $A[i_1]$ в позицию $i_2$ и прежнего числа $A[i_2]$ в позицию $i_1$.

\noindent
\\
Помогите Незнайке составить программу, находящую в недосортированной по убыванию последовательности пару элементов, после обмена которых местами последовательность становится убывающей. Программа считывает десятичное натуральное ненулевое число $N$, а затем последовательность из $N$ записей чисел в модифицированной Незнайкой системе счисления. Во вводе буква с крышкой задаётся двумя символами, например, $\verb|A^|$ означает $\widehat{\texttt{A}}$. Буква с волной также задаётся двумя символами, например, $\verb|B~|$ означает $\widetilde{\texttt{B}}$. Буква с подчёркиванием также задаётся двумя символами, например, $\verb|C_|$ означает $\underline{\texttt{C}}$. Заранее известно, что последовательность является недосортированной по убыванию (в описанном выше смысле). Программа находит номера двух элементов, которые следует переставить, чтобы последовательность стала убывающей, и выводит эти номера. Первым выводится меньший номер, вторым -- больший. Нумерация элементов последовательности начинается с единицы.

\noindent
\\
Пример недосортированной по убыванию последовательности из пяти элементов: \verb|B jw_ D kx~ A|. После обмена местами первого и четвертого элементов она становится отсортированной по убыванию: \verb|kx~ jw_ D B A|

\noindent
\\
\textit{Формат ввода:} В первой строке вводится натуральное число $N$ в десятичной записи: $2 \leq N \leq 500$. В последующих $N$ строках содержатся записи различных неотрицательных чисел $A[i]$ $(i=1..N, A[i]\neq A[j], i\neq j)$ в системе счисления, модифицированной Незнайкой. В каждой записи используются только заглавные и/или строчные латинские буквы, крышка $\verb|^|$, волна $\verb|~|$, подчёркивание $\verb|_|$. Длина каждой записи $A[i]$ не более чем $50$. В каждой строке содержится только запись одного числа.

\noindent
\\
\textit{Формат вывода:} В единственной строке выводятся искомые номера $i_1$ и  $i_2$ $(i_1<i_2)$, записанные в десятичной системе и разделённые одиночным пробелом.

\noindent
\\
\texttt{Ввод примера №1:}\\
\texttt{5}\\
\verb|B|\\
\verb|jw_|\\
\verb|D|\\
\verb|kx~|\\
\verb|A|\\
\texttt{Вывод примера №1:}\\
\verb|1 4|\\
\texttt{Ввод примера №2:}\\
\texttt{4}\\
\verb|m_x_|\\
\verb|m^x^|\\
\verb|m~x~|\\
\verb|mx|\\
\texttt{Вывод примера №2:}\\
\verb|2 3|\\
\texttt{Ввод примера №3:}\\
\texttt{2}\\
\verb|abcdrfghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX|\\
\verb|abcdrfghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWY|\\
\texttt{Вывод примера №3:}\\
\verb|1 2|\\

\noindent\textbf{Решение}

\noindent
В решении стоит использовать массив из 50 элементов со значениями от 0 до 210 как внутреннее представление чисел, записанных 50 разрядами рассматриваемой системы. 210 выбрано верхней границей диапазона, так как потребуется запас для осуществления нормализации числа. Для удобства сравнения старшие разряды стоит хранить в начальных элементах массива. В старших разрядах могут быть незначащие нули. Программа будет в цикле считывать очередной элемент последовательности, осуществлять его нормализацию (т. е. переводить во внутреннее представление в виде массива со значениями разрядов от 0 до 51). Так как заранее известно, что последовательность будет недосортированной по убыванию, то либо будет только одна пара соседних элементов, стоящих не по порядку $(A[i]<A[i+1])$, либо только две таких пары $(A[i]<A[i+1], A[j]<A[j+1], i<j)$. В первом случае ответом будут числа $i$ и $i+1$, во втором -- числа $i$ и $j+1$. Программе достаточно одного прохода по последовательности, осуществляемого во время её ввода, в ходе которого она будет сравнивать нормализованный массив текущего элемента последовательности с нормализованным массивом предыдущего элемента последовательности и запоминать номера пар, в которых числа не по порядку. После обнаружения второй неупорядоченной пары можно не дочитывать последовательность до конца, так как ответ уже известен.

\noindent
При нормализации считанного числа следует начинать с младшего разряда, оставлять в нём остаток от деления нацело значения записанной в разряде цифры на 52, а частное прибавлять к следующему по старшинству разряду. Такие действия проделываются со всеми прочитанными разрядами. Если их меньше 50, то оставшиеся старшие разряды заполняются нулями.

\noindent\textbf{Код возможного решения}
\begin{verbatim}
program NEDOSORT11(input, output);
type    number = array [1..50] of byte;
var  N, I, NUM1, NUM2 : word;
     FLAG : boolean;
     ACURR, APREV : number;
procedure readNumber(var A : number);
var CH : char; I, J : word;
begin for I := 1 to 50 do A[I] := 0;
    read(CH);
    I := 0;
    J := 0;
    while (I < 50) do begin
      case CH of
        'A'..'Z' : begin J := J + 1; A[J] := ord(CH) - ord('A') end;
        'a'..'z' : begin J := J + 1; A[J] := ord(CH) - ord('a') + 26 end;
        '^' : A[J] := A[J] + 52;
        '~' : A[J] := A[J] + 104;
        '_' : A[J] := A[J] + 156;
        end;
        if not (eoln or eof) then begin
            read(CH);
            I := I + 1
        end else I := 50
    end;
    for I := J downto 1 do A[50 - J + I] := A[I];
    for I := 1 to 50 - J do A[I] := 0;
    for I := 50 downto 2 do begin
        A[I - 1] := A[I - 1] + A[I] div 52;
        A[I] := A[I] mod 52
    end;
end;

begin
    readln(N);
    NUM1 := 0;
    NUM2 := 0;
    FLAG := FALSE;
    readNumber(ACURR);
    readln;
    I := 1;
    repeat
        APREV := ACURR;
        readNumber(ACURR);
        if (CompareByte(APREV, ACURR, 50) < 0) then begin
             if (NUM1 = 0) then NUM1 := I
             else begin
                 NUM2 := I;
                 FLAG := TRUE
             end;
        end;
        I := I + 1;
        if (I < N) then readln
    until (I = N) or FLAG;
    if FLAG then write(NUM1, ' ', NUM2 + 1)
    else write(NUM1, ' ', NUM1 + 1)
end.
\end{verbatim}
\newpage\noindent\textbf{Задача 3. Незнайка и рогейн}

\vspace{6pt}\noindent\textbf{Критерий оценивания решений задачи 3}

\noindent
Общим критерием оценивания решения любой задачи является количество тестов, верно пройденных программой, составленной участником. Сначала решение проверяется на тестах из условия. Если не пройден хотя бы один из них, то решение оценивается в $0$ технических баллов. Если тесты из условия пройдены, то решение проверяется на основном наборе тестов. Высчитывается доля (в процентах) верно пройденных тестов из основного набора по отношению к общему количеству тестов в наборе. Полученное количество процентов, округлённое до целого, определяет количество технических баллов за решение.

\vspace{6pt}\noindent\textbf{Технические баллы за задачу 3}

\noindent
За решение задачи начисляется от 0 до 100 технических баллов по критерию, указанному выше. 

\vspace{6pt}\noindent\textbf{Перевод технических баллов в оценку}

\noindent
По каждой задаче определяются самые удачные её решения, отправленные участником. Технические баллы за них суммируются. Полученная сумма умножается на корректировочный коэффициент $\frac{10}{35}$ и округляется до целого. Результат определяет итоговую оценку.

\vspace{6pt}\noindent\textbf{Условия задачи 3}

\noindent
Незнайка побывал в Австралии, где услышал про рогейн -- вид спорта, изобретённый в этой стране. В рогейне от участника требуется быстрое передвижение бегом по пересечённой местности, навыки ориентирования с помощью карты и компаса, а также точное планирование своего маршрута. На карте соревнований по рогейну обозначены контрольные пункты, за посещение каждого из которых начисляется некоторое фиксированное количество очков. Разные пункты могут приносить разные количества очков, или одинаковые, -- это решают устроители соревнований до начала рогейна. Каждый пункт участник может посетить столько раз, сколько пожелает, но очки начисляются только при первом посещении пункта. Цель каждого участника рогейна, набрать наибольшую сумму очков, затратив на передвижение между контрольными пунктами время, не превышающее максимальный предел, установленный организаторами. Передвигаться между любыми двумя контрольными пунктами можно напрямик через лес, либо по дороге, соединяющей два контрольных пункта, если такая дорога имеется.

\noindent
Незнайка уже было решил заняться рогейном, но призадумался над тем, как он будет планировать свой маршрут. Поэтому Незнайка составил программу, которая поможет ему. Входные данные программы содержат сведения об $N$ контрольных пунктах, у каждого из которых известно количество очков за его посещение -- $p_i$. Маршрут Незнайки начинается в пункте 1. За время, не превышающее заданное время $T$, Незнайка должен посетить выбранные им контрольные пункты и успеть вернуться в пункт 1. Выбирать контрольные пункты для маршрута Незнайка должен так, чтобы набрать максимально возможную сумму очков. Про любые два контрольных пункта $u$ и $v$ Незнайка имеет сведения о том, сколько времени он потратит на передвижение от пункта $u$ до пункта $v$ напрямик через лес и о том, есть ли дорога, соединяющая пункты $u$ и $v$, и если она есть, то сколько времени занимает передвижение по ней. Программа находит набор контрольных пунктов, которые можно успеть посетить и набрать при этом наибольшую сумму очков. При выводе результата номера пунктов сортируются по возрастанию. Набор пунктов всегда начинается с 1. В наборе пункты не повторяются, даже если пункт при передвижении был посещён неоднократно, его номер в ответе выводится один раз. В частности, набор из более чем одного пункта заканчивается не на 1, так как никакой номер пункта не повторяется. Если программа находит несколько наборов пунктов, то она оставляет лишь те, которые имеют наименьший размер. Если после этого остаётся один вариант, то он и является ответом. Если остаётся несколько вариантов, то программа упорядочивает наборы пунктов лексикографически и считает ответом набор пунктов, оказавшийся на первом месте.

\noindent
Составьте свою программу, дающую те же ответы, что и программа, составленная Незнайкой.

\noindent
Рассмотрим один пример. Пусть имеется три пункта. Пусть передвижение по лесу между любой парой пунктов занимает 9 минут. Пусть между любой парой пунктов есть дорога, движение по которой занимает 1 минуту. Пусть предельное время составляет 10 минут. Пусть количества очков за посещения пунктов равны 1, 2 и 3, соответственно. Программа найдёт два набора пунктов: 1) \verb|1 2 3| и 2) \verb|1 3 2|. После сортировки номеров пунктов по возрастанию оба набора запишутся одинаково: \verb|1 2 3|. Эта запись и будет ответом.

\noindent
Рассмотрим ещё один пример. Пусть, как и ранее, имеется три пункта. Пусть передвижение по лесу между любой парой пунктов занимает 9 минут. Пусть между первым и вторым пунктом есть дорога, движение по которой занимает 1 минуту. Пусть между вторым и третьим пунктом есть дорога, движение по которой занимает 1 минуту. Пусть предельное время составляет 4 минуты. Пусть количества очков за посещения пунктов равны 1, 3 и 5, соответственно. Программа найдёт один маршрут подходящей длительности, передвигаясь по которому удастся посетить все три пункта, успеть вернуться в первый и заработать 9 очков: $1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$. Единственный набор пунктов этого маршрута будет ответом: \verb|1 2 3|.

\noindent
Рассмотрим последний пример. Пусть, как и ранее, имеется три пункта. Пусть передвижение по лесу между любой парой пунктов занимает 9 минут. Пусть между первым и вторым пунктом есть дорога, движение по которой занимает 1 минуту. Пусть между первым и третьим пунктом есть дорога, движение по которой занимает 1 минуту. Пусть предельное время составляет 2 минуты. Пусть количества очков за посещения пунктов равны 1, 5 и 5, соответственно. В таких условиях есть два маршрута подходящей длительности, передвигаясь по которым удастся посетить два пункта, успеть вернуться в первый и заработать 6 очков: $1 \rightarrow 2 \rightarrow 1$ и $1 \rightarrow 3 \rightarrow 1$. Разных наборов пунктов у этих маршрутов будет два: 1) \verb|1 2| и 2) \verb|1 3|. Лексикографически первый набор предшествует второму. Он и будет ответом.
      
\noindent
\\
\textit{Формат ввода:}\\ В первой строке вводятся $3$ натуральных числа $N~ T~ M$ $(N\leq 10,~ T\leq 10^9,~ M\leq \frac{N(N-1)}{2})$ -- количество контрольных пунктов, максимальный предел времени и количество дорог. Во второй строке даны $N$ натуральных чисел -- количества очков за посещение контрольных пунктов -- $p_1, \dots, p_N (p_i \leq 10^9)$. В следующих $N$ строках дана таблица $G$ размера $N\times N$ из натуральных чисел, где $G[i][j] = G[j][i] \leq 10^9$, и $G[i][j]$ задаёт время, которое потребуется для перемещения между пунктами $i$ и $j$ напрямик через лес. Гарантируется, что $G[i][i] = 0$. Затем в $M$ строках даны сведения о дорогах в формате $u_i~ v_i~  d_i$ $(1\leq u_i, v_i \leq N , u_i\ne v_i, 1\leq d_i\leq 10^9)$. Любая из этих строк сообщает о том, что из пункта $u_i$ можно добежать до пункта $v_i$ по дороге за $d_i$ минут. Любая дорога допускает движение в обоих направлениях (из $u_i$ до $v_i$ и наоборот), и время, затраченное на движение по ней, не зависит от направления движения. Любая пара пунктов может быть соединена не более чем одной дорогой. Если проложена дорога из $u_i$ до $v_i$, то ещё одной дороги из $v_i$ до $u_i$ быть не может.

\noindent
\\
\textit{Формат вывода:}\\ В первой строке программа выводит $K$ -- количество пунктов наборе, составленном так, как описано выше. Во второй строке программа выводит номера пунктов по возрастанию, разделяя одиночными пробелами, не ставя пробел после последнего пункта в наборе: $n_1~ n_2~\dots~ n_K$, где  $n_1= 1$ и $n_K \neq 1$ при $K \neq 1$.

\noindent
\\
\texttt{Ввод примера №1:}\\
\verb|3 10 2|\\
\verb|1 4 3|\\
\verb|0 9 9|\\
\verb|9 0 9|\\
\verb|9 9 0|\\
\verb|1 2 1|\\
\verb|2 3 1|\\
\texttt{Вывод примера №1:}\\
\verb|3|\\
\verb|1 2 3|\\
\texttt{Ввод примера №2:}\\
\verb|3 10 1|\\
\verb|1 4 5|\\
\verb|0 9 9|\\
\verb|9 0 9|\\
\verb|9 9 0|\\
\verb|1 2 1|\\
\texttt{Вывод примера №2:}\\
\verb|2|\\
\verb|1 2|\\
\texttt{Ввод примера №3:}\\
\verb|3 10 1|\\
\verb|1 4 5|\\
\verb|0 9 9|\\
\verb|9 0 9|\\
\verb|9 9 0|\\
\verb|1 2 6|\\
\texttt{Вывод примера №3:}\\
\verb|1|\\
\verb|1|\\

\noindent\textbf{Пояснения по решению задачи 3}

\noindent
Задача состоит в том, чтобы составить маршрут во взвешенном неориентированном графе длины меньше параметра $T$, который пройдет через вершины с максимальной суммой очков. 

\noindent
Заметим, что дороги можно использовать только, если она укорачивает передвижение между пунктами, а значит, для каждой дороги $(u,v,w)$, где $u,v$ -- это номера пунктов, а $w$ -- это время передвижения между $u$ и $v$ по дороге можно обновить значение матрицы смежности $G[u][v] = \min(G[u][v],w)$. 

\noindent
Далее отметим, что параметр $N$ довольно мал, что позволяет нам перебрать все перестановки $P = (a_1, \dots , a_{n-1})$ посещения вершин, где $a_i \in \overline{2,n}$ и $a_i \ne a_j$ при $i \ne j$. Каждая такая перестановка будет описывать последовательность первых посещений соответствующих пунктов. Тогда ответ на вопрос, сколько времени потребуется, чтобы посетить вершины $(a_1, \dots , a_{k})$ находится, как $d[1][a_1]+d[a_1][a_2] + \dots + d[a_k][1]$, где $d[i][j] -- $ это минимальное время, необходимое для передвижение от $i$  пункта до $j$. Подсчет суммы можно вести, пока ее значение меньше $T$. Итого каждая перестановка может лишь один раз попытаться обновить максимальное количество очков за пункты. Алгоритм достаточно эффективен, если заранее посчитать $d[i][j]$.

\noindent
Вычислить $d[i][j]$  можно несколькими способами:
\begin{enumerate}
\item Для каждого пункта запустить алгоритм Дейкстры.
\item Сразу найти все кратчайшие расстояния с помощью алгоритма Флойда - Уоршелла. 
\end{enumerate}

\noindent
В конце необходимо вывести вершины, встретившиеся в лучшей перестановке в порядке возрастания.

\noindent
\\
\textbf{Код возможного решения}
\begin{verbatim}
#include <bits/stdc++.h>

using namespace std;

const int inf = 1'000'000'001;

int main() {
    // read data
    int N, T, M;
    cin >> N >> T >> M;
    vector<int> p(N);
    for (int i = 0; i < N; ++i) cin >> p[i];
    vector<vector<int>> G(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) cin >> G[i][j];
    int u, v, d;
    for (int i = 0; i < M; ++i) {
        cin >> u >> v >> d;
        u--;
        v--;
        G[u][v] = min(G[u][v], d);
        G[v][u] = min(G[v][u], d);
    }
    // preprocessing
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            if (i == j) continue;
            if (G[i][j] == 0) G[i][j] = inf;
        }

    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);

    // main algorithm
    vector<int> route;
    for (int i = 1; i < N; ++i) route.push_back(i);
    long long max_score = p[0];
    vector<int> max_route;
    do {
        long long iter_score = p[0];
        long long iter_time = 0;
        int iter_pos = 0;
        for (int checkpoint : route) {
            if (G[iter_pos][checkpoint] >= inf) continue;
            if (G[checkpoint][0] >= inf) continue;
            if (iter_time + G[iter_pos][checkpoint] + G[checkpoint][0] <= T) {
                iter_time += G[iter_pos][checkpoint];
                iter_score += p[checkpoint];
                iter_pos = checkpoint;
            } else
                break;
        }
        if (max_score < iter_score) {
            max_score = iter_score;
            max_route.clear();
            for (int checkpoint : route) {
                if (checkpoint == iter_pos) {
                    max_route.push_back(checkpoint);
                    break;
                }
                max_route.push_back(checkpoint);
            }
        }
    } while (next_permutation(route.begin(), route.end()));
    // print answer
    set<int> ans = {1};
    for (int checkpoint : max_route) ans.insert(checkpoint + 1);
    cout << ans.size() << endl;
    for (int checkpoint : ans) cout << checkpoint << ' ';
    cout << endl;
}
\end{verbatim}
\newpage\vspace{6pt}\noindent\textbf{Задача 4. Незнайка и химия}

\vspace{6pt}\noindent\textbf{Критерий оценивания решений задачи 4}

\noindent
Общим критерием оценивания решения любой задачи является количество тестов, верно пройденных программой, составленной участником. Сначала решение проверяется на тестах из условия. Если не пройден хотя бы один из них, то решение оценивается в $0$ технических баллов. Если тесты из условия пройдены, то решение проверяется на основном наборе тестов. Высчитывается доля (в процентах) верно пройденных тестов из основного набора по отношению к общему количеству тестов в наборе. Полученное количество процентов, округлённое до целого, определяет количество технических баллов за решение.

\vspace{6pt}\noindent\textbf{Технические баллы за задачу 4}

\noindent
За решение задачи начисляется от 0 до 100 технических баллов по критерию, указанному выше. 

\vspace{6pt}\noindent\textbf{Перевод технических баллов в оценку}

\noindent
По каждой задаче определяются самые удачные её решения, отправленные участником. Полученная сумма умножается на корректировочный коэффициент $\frac{10}{35}$ и округляется до целого. Результат определяет итоговую оценку.\\

\noindent\textbf{Условия задачи 4}

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

\noindent
\\Молекулы состоят из атомов. Атом — это либо одна заглавная латинская буква, либо заглавная латинская буква, за которой идут одна или более строчных латинских букв. Примеры обозначения атомов: H, El, Elerium. Если после обозначения атома записано положительное целое число, оно обозначает число атомов этого типа. Молекула состоит из атомов с указанием числа повторений. Примеры молекул: H2O, C2H5OLi. для группировки в записи молекулы могут использоваться круглые или квадратные скобки, но тогда число повторений относится ко всей группе атомов в скобках. Например, [(CH2)10HSi]2.

\noindent
\\Формула реакции описывает превращение химических веществ. В процессе реакции одни молекулы превращаются в другие молекулы. Формула реакции записывается в виде I1+I2+I3...=O1+O2.... Молекулы с левой стороны от знака равенства — исходные вещества, а молекулы с правой части — результат реакции. Молекулы в левой и правой части разделяются знаком сложения. И в левой, и в правой части формулы реакции могут находится одна или более обозначений молекул. Перед обозначением молекулы может быть записано положительное целое число, обозначающее количество молекул в реакции. Пример реакции: 2H2+O2=2H2O.

\noindent
\\В правильно записанной формуле должен выполняться закон сохранения вещества. Количество атомов каждого вещества в левой части формулы должно быть равно количеству атомов в правой части формулы реакции. Например, реакция H2+O2=H2O или реакция 3H2+CO2=H2O записаны неправильно.

\noindent
\\Напишите программу, которая из возможно неправильной записи химической реакции получит правильную запись. Преобразованная запись химической реакции должна удовлетворять следующим требованиям:\\
$\circ$ Молекулы веществ в левых и правых частях формулы должны следовать в порядке их первого вхождения в левую и правую части соответственно.\\
$\circ$ Если одна и та же молекула входит в левую или правую части формулы несколько раз, все вхождения, кроме первого игнорируются. Запись молекулы для этого должна быть посимвольно совпадающей.\\
$\circ$ Если в левой или правой части формулы полностью отсутствуют атомы, нужные в другой части, недостающие атомы должны быть записаны в лексикографическом порядке в соответствующей части формулы после веществ из исходной формулы.\\
$\circ$ Должен выполняться закон сохранения вещества.\\
$\circ$ Числовые коэффициенты перед молекулами должны быть минимально возможными. Поэтому формула реакции 4H2+2O2=4H2O неправильная.

\noindent
\\Формулы реакции вводятся на стандартном потоке ввода по одной формуле на строке. Исправленные формулы должны быть выведены на стандартный поток вывода по одной формуле на строке.

\noindent
Для представления количества атомов в левой и правой частях формулы и для всех промежуточных вычислений достаточно положительных знаковых 32-битных целых чисел.

\noindent
\\
\texttt{Формат ввода:}\\ Формулы реакции вводятся на стандартном потоке ввода по одной формуле на строке. Количество атомов в левой и правой частях и входной формулы, и выходной формулы представимо положительным знаковым 32-битным целым числом. Длина одной входной строки не превышает 100000 байт. Суммарный размер всех входных строк не превышает 1000000 байт.

\noindent
\\
\texttt{Формат вывода:}\\ Исправленные формулы должны быть выведены на стандартный поток вывода по одной формуле на строке.

\noindent
\\
\texttt{Пример ввода:}\begin{verbatim}
H2+O2=H2O
Si+O2=SiO2
C+O2+C+O2+C=CO2
(He[C2(O2Mg)4(O2Fe)2]2N3)2H3=(He(C2(O2Mg)4(O2Fe)2)2N3)2H3F4
\end{verbatim}\texttt{Пример вывода:}\begin{verbatim}
2H2+O2=2H2O
Si+O2=SiO2
C+O2=CO2
(He[C2(O2Mg)4(O2Fe)2]2N3)2H3+4F=(He(C2(O2Mg)4(O2Fe)2)2N3)2H3F4
\end{verbatim}
%\noindent\textbf{Решение}
%
%\noindent
%...
%
%\noindent
%\\
\textbf{Код возможного решения}
\begin{verbatim}
use std::{collections::{HashMap, HashSet}, error::Error, fmt::{Display, Write}};

#[derive(Debug, Clone)]
enum Token<'a> {
    End,
    Open(u8),
    Close(u8),
    Equals,
    Atom(&'a str),
    Num(i32),
    Plus,
    Bracket(&'a str, Box<Token<'a>>, &'a str),
    Counted(Box<Token<'a>>, i32),
    Molecule(Vec<Box<Token<'a>>>, &'a str),
    Component(i32,Box<Token<'a>>),
    Side(Vec<Box<Token<'a>>>),
    Equation(Box<Token<'a>>,Box<Token<'a>>),
}

impl<'a> Display for Token<'a> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Token::Open(c) => f.write_char(*c as char),
            Token::Close(c) => f.write_char(*c as char),
            Token::Equals => f.write_char('='),
            Token::Atom(s) => f.write_str(*s),
            Token::Num(x) => f.write_fmt(format_args!("{}", *x)),
            Token::Plus => f.write_char('+'),
            Token::Bracket(ob, t, cb) => {
                f.write_str(*ob)?;
                t.fmt(f)?;
                f.write_str(*cb)
            },
            Token::Counted(t, cnt) => {
                t.fmt(f)?;
                if *cnt > 1 {
                    f.write_fmt(format_args!("{}", *cnt))?;
                }
                Ok(())
            },
            Token::Molecule(_, s) => {
                f.write_str(*s)?;
                /*
                for i in 0..v.len() {
                    v[i].fmt(f)?;
                }
                */
                Ok(())
            },
            Token::Component(cnt, t) => {
                if *cnt > 1 {
                    f.write_fmt(format_args!("{}", *cnt))?;
                }
                t.fmt(f)?;
                Ok(())
            },
            Token::Side(v) => {
                for i in 0..v.len() {
                    if i > 0 {
                        f.write_char('+')?;
                    }
                    v[i].fmt(f)?;
                }
                Ok(())
            },
            Token::Equation(lhs, rhs) => {
                lhs.fmt(f)?;
                f.write_char('=')?;
                rhs.fmt(f)
            },
            _ => panic!(),
        }
    }
}

#[derive(Debug, Clone)]
struct ParseError {
    msg: &'static str,
    pos: usize,
}
impl ParseError {
    fn new(msg: &'static str, pos: usize) -> Self {
        Self { msg, pos }
    }
}
impl Display for ParseError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_fmt(format_args!("parse error {} at pos {}", self.msg, self.pos))
    }
}
impl Error for ParseError {
}

struct Parser<'a> {
    s: &'a [u8],
    len: usize,
    i: usize,
    t: Token<'a>,
    token_i: usize,
    atom_map: HashMap<&'a str, i32>,
    atom_vec: Vec<&'a str>,
    counts: Vec<Vec<i32>>,
}

impl<'a> Parser<'a> {
    fn new(s: &'a str) -> Self {
        Self {
            s: s.as_bytes(),
            len: s.len(),
            i: 0,
            t: Token::End,
            token_i: 0,
            atom_map: HashMap::new(),
            atom_vec: Vec::new(),
            counts: vec![Vec::new(), Vec::new()],
        }
    }
    fn next_token(&mut self) -> Result<(), Box<dyn Error>> {
        self.token_i = self.i;
        if self.i >= self.len {
            self.t = Token::End;
        } else if self.s[self.i] >= b'0' && self.s[self.i] <= b'9' {
            let mut val = 0;
            while self.i < self.len && self.s[self.i] >= b'0' && self.s[self.i] <= b'9' {
                val = val * 10 + (self.s[self.i] - b'0') as i32;
                self.i += 1;
            }
            self.t = Token::Num(val);
        } else if self.s[self.i] >= b'A' && self.s[self.i] <= b'Z' {
            let beg = self.i;
            self.i += 1;
            while self.i < self.len && self.s[self.i] >= b'a' && self.s[self.i] <= b'z' {
                self.i += 1;
            }
            self.t = Token::Atom(std::str::from_utf8(&self.s[beg..self.i]).unwrap());
        } else if self.s[self.i] == b'(' || self.s[self.i] == b'[' {
            self.t = Token::Open(self.s[self.i]);
            self.i += 1;
        } else if self.s[self.i] == b')' || self.s[self.i] == b']' {
            self.t = Token::Close(self.s[self.i]);
            self.i += 1;
        } else if self.s[self.i] == b'=' {
            self.t = Token::Equals;
            self.i += 1;
        } else if self.s[self.i] == b'+' {
            self.t = Token::Plus;
            self.i += 1;
        } else {
            return Err(Box::new(ParseError::new("invalid char", self.i)));
        }
        Ok(())
    }

    fn counted(&mut self) -> Result<Token<'a>, Box<dyn Error>> {
        let b: Box<Token<'a>>;
        match self.t {
            Token::Atom(_) => {
                b = Box::new(self.t.clone());
                self.next_token()?;
            },
            Token::Open(oc) => {
                let ob = std::str::from_utf8(&self.s[self.i-1..self.i]).unwrap();
                self.next_token()?;
                let m = self.molecule()?;
                if let Token::Close(cc) = self.t {
                    if (oc == b'(' && cc == b')') || (oc == b'[' && cc == b']') {
                        let cb = std::str::from_utf8(&self.s[self.i-1..self.i]).unwrap();
                        self.next_token()?;
                        b = Box::new(Token::Bracket(ob, Box::new(m), cb));
                    } else {
                        return Err(Box::new(ParseError::new("bracket mismatch", self.i)));
                    }
                } else {
                    return Err(Box::new(ParseError::new("expect closing bracket", self.i)));
                }
            },
            _ => {
                return Err(Box::new(ParseError::new("unexpected token", self.i)));
            },
        }
        let mut cnt = 1;
        if let Token::Num(cc) = self.t {
            cnt = cc;
            self.next_token()?;
        }
        Ok(Token::Counted(b, cnt))
    }
    fn molecule(&mut self) -> Result<Token<'a>, Box<dyn Error>> {
        let mut v: Vec<Box<Token<'a>>> = Vec::new();
        let beg = self.token_i;
        loop {
            match self.t {
                Token::Open(_) | Token::Atom(_) => v.push(Box::new(self.counted()?)),
                _ => break,
            }
        }
        let end = self.token_i;
        Ok(Token::Molecule(v, std::str::from_utf8(&self.s[beg..end]).unwrap()))
    }
    fn component(&mut self) -> Result<Token<'a>, Box<dyn Error>> {
        let mut koef = 1;
        if let Token::Num(kk) = self.t {
            koef = kk;
            self.next_token()?;
        }
        let m = self.molecule()?;
        Ok(Token::Component(koef, Box::new(m)))
    }
    fn side(&mut self) -> Result<Token<'a>, Box<dyn Error>> {
        let mut comps: Vec<Box<Token<'a>>> = Vec::new();
        comps.push(Box::new(self.component()?));
        while let Token::Plus = self.t {
            self.next_token()?;
            comps.push(Box::new(self.component()?));
        }
        Ok(Token::Side(comps))
    }
    fn equation(&mut self) -> Result<Token<'a>, Box<dyn Error>> {
        let s1 = self.side()?;
        if let Token::Equals = self.t {
            self.next_token()?;
            let s2 = self.side()?;
            Ok(Token::Equation(Box::new(s1), Box::new(s2)))
        } else {
            Err(Box::new(ParseError::new("= expected", self.i)))
        }
    }
    fn parse(&mut self) -> Result<Token<'a>, Box<dyn Error>> {
        self.next_token()?;
        let root = self.equation()?;
        if let Token::End = self.t {
            Ok(root)
        } else {
            Err(Box::new(ParseError::new("EOF expected", self.i)))
        }
    }

    fn reset_component_count(&mut self, node: &mut Token<'a>) {
        match node {
            Token::Component(cnt, _) => {
                *cnt = 1;
            },
            Token::Side(v) => {
                for item in v {
                    self.reset_component_count(item.as_mut());
                }
            },
            Token::Equation(lhs, rhs) => {
                self.reset_component_count(lhs.as_mut());
                self.reset_component_count(rhs.as_mut());
            },
            _ => panic!(),
        }
    }

    fn set_component_count(&mut self, node: &mut Token<'a>, cnts: &[i32]) 
	-> usize {
        match node {
            Token::Component(cnt, _) => {
                *cnt = cnts[0];
                return 1;
            },
            Token::Side(v) => {
                let mut res = 0;
                for t in v {
                    res += self.set_component_count(t.as_mut(), &cnts[res..]);
                }
                return res;
            },
            Token::Equation(lhs, rhs) => {
                let cnt = self.set_component_count(lhs.as_mut(), cnts);
                let cnt2 = self.set_component_count(rhs.as_mut(), &cnts[cnt..]);
                return cnt + cnt2;
            },
            _ => panic!(),
        }
    }

    fn remove_duplicates(&mut self, node: &mut Token<'a>) {
        match node {
            Token::Side(v) => {
                let mut ms: HashSet<&'a str> = HashSet::new();
                let mut j = 0;
                for i in 0..v.len() {
                    let m: &'a str;
                    if let Token::Component(_, mol) = v[i].as_mut() {
                        if let Token::Molecule(_, mm) = mol.as_mut() {
                            m = *mm;
                        } else {
                            panic!();
                        }
                    } else {
                        panic!();
                    }
                    if !ms.contains(m) {
                        ms.insert(m);
                        v.swap(i, j);
                        j += 1;
                    }
                }
                v.resize_with(j, || Box::new(Token::End));
            },
            Token::Equation(lhs, rhs) => {
                self.remove_duplicates(lhs.as_mut());
                self.remove_duplicates(rhs.as_mut());
            },
            _ => panic!(),
        }
    }
    fn collect_atoms(&mut self, node: &Token<'a>, am: &mut HashMap<&'a str, i32>, av: &mut Vec<&'a str>) {
        match node {
            Token::Atom(s) => {
                am.entry(*s).or_insert_with(|| {
                    let len = av.len() as i32;
                    av.push(*s);
                    len
                });
            },
            Token::Bracket(_, t, _) => {
                self.collect_atoms(t.as_ref(), am, av);
            },
            Token::Counted(t, _) => {
                self.collect_atoms(t, am, av);
            },
            Token::Molecule(v, _) => {
                for i in 0..v.len() {
                    self.collect_atoms(&v[i], am, av);
                }
            },
            Token::Component(_, t) => {
                self.collect_atoms(t.as_ref(), am, av);
            },
            Token::Side(v) => {
                for i in 0..v.len() {
                    self.collect_atoms(&v[i], am, av);
                }
            },
            Token::Equation(lhs, rhs) => {
                self.collect_atoms(lhs.as_ref(), am, av);
                self.collect_atoms(rhs.as_ref(), am, av);
            },
            _ => (),
        }
    }
    fn compute_presence(&mut self, node: &Token<'a>, flag: &mut[bool]) {
        match node {
            Token::Atom(a) => {
                flag[self.atom_map[*a] as usize] = true;
            },
            Token::Bracket(_, t, _) => {
                self.compute_presence(t.as_ref(), flag);
            },
            Token::Counted(t, _) => {
                self.compute_presence(t.as_ref(), flag);
            },
            Token::Molecule(v, _) => {
                for i in 0..v.len() {
                    self.compute_presence(v[i].as_ref(), flag);
                }
            },
            Token::Component(_, t) => {
                self.compute_presence(t.as_ref(), flag);
            },
            Token::Side(v) => {
                for i in 0..v.len() {
                    self.compute_presence(v[i].as_ref(), flag);
                }
            }
            _ => panic!(),
        }
    }
    fn do_insert_missing(&mut self, node: &mut Token<'a>, p: &[bool]) {
        match node {
            Token::Side(v) => {
                for i in 0..p.len() {
                    if !p[i] {
                        let a = Box::new(Token::Atom(self.atom_vec[i]));
                        let c = Box::new(Token::Counted(a, 1));
                        let m = Box::new(Token::Molecule(vec![c], self.atom_vec[i]));
                        let cc = Box::new(Token::Component(1, m));
                        v.push(cc);
                    }
                }
            },
            _ => panic!(),
        }
    }
    fn insert_missing(&mut self, node: &mut Token<'a>) {
        match node {
            Token::Equation(lhs, rhs) => {
                let mut lhp = vec![false; self.atom_vec.len()];
                self.compute_presence(lhs.as_ref(), &mut lhp);
                let mut rhp = vec![false; self.atom_vec.len()];
                self.compute_presence(rhs.as_ref(), &mut rhp);
                self.do_insert_missing(lhs.as_mut(), &lhp);
                self.do_insert_missing(rhs.as_mut(), &rhp);
            },
            _ => panic!(),
        }
    }
    fn count_atoms(&mut self, node: &Token<'a>, cnt: &mut [i32], mult: i32) {
        match node {
            Token::Atom(s) => cnt[self.atom_map[*s] as usize] += mult,
            Token::Bracket(_, t, _) => self.count_atoms(t.as_ref(), cnt, mult),
            Token::Counted(t, v) => self.count_atoms(t.as_ref(), cnt, mult * *v),
            Token::Molecule(v, _) => {
                for i in 0..v.len() {
                    self.count_atoms(v[i].as_ref(), cnt, mult);
                }
            },
            Token::Component(v, t) => self.count_atoms(t.as_ref(), cnt, mult * *v),
            _ => panic!(),
        }
    }
    fn count_atoms_side(&mut self, node: &Token<'a>, cnt: &mut Vec<Vec<i32>>) {
        match node {
            Token::Side(v) => {
                for i in 0..v.len() {
                    let mut cc = vec![0; self.atom_vec.len()];
                    self.count_atoms(v[i].as_ref(), &mut cc, 1);
                    cnt.push(cc);
                }
            },
            _ => panic!(),
        }
    }
    fn count_atoms_equation(&mut self, node: &Token<'a>) {
        match node {
            Token::Equation(lhs, rhs) => {
                let mut lc: Vec<Vec<i32>> = Vec::new();
                self.count_atoms_side(lhs.as_ref(), &mut lc);
                let mut rc: Vec<Vec<i32>> = Vec::new();
                self.count_atoms_side(rhs.as_ref(), &mut rc);
                self.counts = Vec::new();
                for v in lc {
                    self.counts.push(v);
                }
                for mut v in rc {
                    for x in &mut v {
                        *x = -*x;
                    }
                    self.counts.push(v);
                }
            },
            _ => panic!(),
        }
    }
    fn apply(mat: &Vec<Vec<i32>>, v: &[i32], out: &mut [i32]) {
        // mat: n rows; m columns; v: n; out: m
        out.fill(0);
        let rows = mat.len();
        let cols = out.len();
        for r in 0..rows {
            for c in 0..cols {
                out[c] += mat[r][c] * v[r];
            }
        }
    }
    fn is_zero(v: &[i32]) -> bool {
        for &x in v.iter() {
            if x != 0 {
                return false;
            }
        }
        true
    }
    fn apply_bool(mat: &Vec<Vec<i32>>, v: &[i32], out: &mut [i32]) -> bool {
        Self::apply(mat, v, out);
        Self::is_zero(out)
    }
    fn next_vector(v: &mut [i32], lim: &mut i32, limcnt: &mut usize) -> bool {
        if *limcnt == v.len() {
            v.fill(1);
            *lim += 1;
            *limcnt = 0;
        }
        loop {
            let mut i = 0;
            while i < v.len() {
                if v[i] == *lim {
                    *limcnt -= 1;
                    v[i] = 1;
                } else {
                    v[i] += 1;
                    if v[i] == *lim {
                        *limcnt += 1;
                    }
                    break;
                }
                i += 1;
            }
            if *limcnt > 0 {
                break;
            }
        }
        false
    }
}

fn solve(s : &str) -> Result<String, Box<dyn std::error::Error>> {
    let mut p = Parser::new(s);
    let mut root = p.parse()?;
    //println!("Parsed: {}", root);
    p.reset_component_count(&mut root);
    //println!("Reset count: {}", root);
    p.remove_duplicates(&mut root);
    //println!("Remove dups: {}", root);
    let mut atom_map: HashMap<&str, i32> = HashMap::new();
    let mut atom_vec: Vec<&str> = Vec::new();
    p.collect_atoms(&root, &mut atom_map, &mut atom_vec);
    atom_vec.sort();
    atom_map.clear();
    for i in 0..atom_vec.len() {
        atom_map.insert(atom_vec[i], i as i32);
    }
    //println!("map: {:?}", atom_map);
    //println!("vec: {:?}", atom_vec);
    p.atom_map = atom_map;
    p.atom_vec = atom_vec;
    p.insert_missing(&mut root);
    //println!("Append missing: {}", root);
    p.count_atoms_equation(&root);
    //println!("Counts: {:?}", p.counts);
    let mut cnts = vec![1; p.counts.len()];
    let mut lim = 1;
    let mut limcnt = p.counts.len();
    let mut out = vec![0; p.counts[0].len()];
    loop {
        if Parser::apply_bool(&p.counts, &cnts, &mut out) {
            p.set_component_count(&mut root, &cnts);
            return Ok(format!("{}", root));
        }
        if Parser::next_vector(&mut cnts, &mut lim, &mut limcnt) {
            return Ok("BAD".to_string());
        }
    }
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let mut buf = String::new();
    while std::io::stdin().read_line(&mut buf)? > 0 {
        println!("{}", solve(buf.trim())?);
        buf.clear();
    }
    Ok(())
}
\end{verbatim}
\newpage\noindent\textbf{Задача 5. Незнайка и эпидемия}

\vspace{6pt}\noindent\textbf{Критерий оценивания решений задачи 5}

\noindent
Общим критерием оценивания решения любой задачи является количество тестов, верно пройденных программой, составленной участником. Сначала решение проверяется на тестах из условия. Если не пройден хотя бы один из них, то решение оценивается в $0$ технических баллов. Если тесты из условия пройдены, то решение проверяется на основном наборе тестов. Высчитывается доля (в процентах) верно пройденных тестов из основного набора по отношению к общему количеству тестов в наборе. Полученное количество процентов, округлённое до целого, определяет количество технических баллов за решение.

\vspace{6pt}\noindent\textbf{Технические баллы за задачу 5}

\noindent
За решение задачи начисляется от 0 до 100 технических баллов по критерию, указанному выше. 

\vspace{6pt}\noindent\textbf{Перевод технических баллов в оценку}

\noindent
По каждой задаче определяются самые удачные её решения, отправленные участником. Технические баллы за них суммируются. Полученная сумма умножается на корректировочный коэффициент $\frac{10}{35}$ и округляется до целого. Результат определяет итоговую оценку.\\ 

\noindent\textbf{Условия задачи 5}

\noindent
Цветочный город поразила эпидемия загадочного заболевания пурпурного пятого пальца. Доктору Пилюлькину удалось определить, что заболевание имеет вирусную природу и передается при непосредственном контакте мизинцами. Удалось также выявить <<нулевого>> пациента, который приехал зараженным из Зеленого города, и отследить все контакты, приведшие к заражениям.\\

\noindent
Вирус болезни кодирует свою наследственную информацию в РНК длины оснований. Было установлено, что при каждом заражении происходила мутация ровно одного из оснований РНК, и было установлено положение мутировавшего основания в РНК. РНК вируса можно представить как строку длины , состоящую из 4 букв $A$, $C$, $G$, $U$.\\

\noindent
Если бы мутаций не было, то у всех заболевших РНК вируса полностью совпадали, но каждая мутация приводит к тому, что неизменная часть РНК вируса становится все меньше и меньше. Напишите программу, которая для двух пациентов определит длину самого большого совпадающего фрагмента РНК вирусов, заразивших этих пациентов. Например, если РНК вируса первого пациента кодируется как $AAGCUUCAG$, а РНК вируса второго пациента кодируется как $ACGCUUAAG$, то у этих РНК есть три совпадающих фрагмента: $A$, $GCUU$ и $AG$. Самый длинный фрагмент имеет длину 4. Обратите внимание, что фрагменты в двух РНК должны находиться на тех же самых местах.\\

\noindent
У доктора Пилюлькина компьютер, к сожалению, достаточно старый, поэтому ваша программа должна экономно использовать ресурсы. Обратите внимание на ограничения по памяти в этой задаче. Memory RSS limit: 128Mb Stack limit: 8Mb.

\noindent
\\
\texttt{Формат ввода:}\\Первая строка входных данных содержит три целых положительных числа $M$, $N$, $K$. $M$ -- это длина РНК вируса $(M < 801)$, $N$ -- количество пациентов $(N < 1000001)$, $K$ -- количество запросов на определение длины $(K < 1001)$. Следующие $N-1$ строк содержат описания контактов, приведших к заражению. Каждый контакт -- это три числа $S$, $D$, $B$, обозначающие, что пациент $S$ заразил пациента $D$ (пациенты нумеруются подряд от $1$ до $N$ включительно), при этом произошла мутация в основании $B$ (основания нумеруются подряд от $0$ до $M-1$ включительно). Гарантируется, что контакты описывают одно дерево заражений, в котором <<нулевой>> пациент имеет номер 1. Следующие $K$ строк содержат описания запросов в виде пар чисел $P$, $Q$, где $P$ и $Q$ — номера пациентов, для которых нужно определить гарантированную длину самого большого совпадающего фрагмента РНК. Поскольку не даны сами РНК вирусов, а только места мутаций, возможно, что совпадающие фрагменты могут быть и длиннее за счет мутаций, которые компенсируют друг друга. Это учитывать не нужно. 

\noindent
\\
\texttt{Формат вывода:}\\Для каждого запроса выведите одно число -- длину самого большого совпадающего фрагмента РНК.

\noindent
\\
\texttt{Пример ввода:}\begin{verbatim}
16 3 1
1 2 6
2 3 12
3 1
\end{verbatim}\texttt{Пример вывода:}\begin{verbatim}
6
\end{verbatim}
%\noindent\textbf{Решение}
%
%\noindent
%...
%
%\noindent
%\\
\textbf{Код возможного решения}
\begin{verbatim}
use std::error::Error;

pub struct State {
    pub n: usize, // number of nodes; nodes are numbered 0..n
    m: usize, // size of the DNA
    uplink: Vec<(u32,u32)>,
    downlink: Vec<Vec<(u32, u32)>>,
    first_entry: Vec<u32>,
    depths: Vec<u32>,
    depth_nodes: Vec<u32>,
    rmq_idx: Vec<Vec<u32>>,
}

impl State {
    fn new(n: usize, m: usize, uplink: Vec<(u32,u32)>, downlink: Vec<Vec<(u32, u32)>>) 
	-> Self {
        Self {
            n,
            m,
            uplink,
            downlink,
            first_entry: vec![u32::MAX; n],
            depths: Vec::new(),
            depth_nodes: Vec::new(),
            rmq_idx: Vec::new(),
        }
    }

    fn make_depths(&mut self) {
        let mut stk: Vec<(u32, u32, u32)> = Vec::new(); // (node, index, depth)
        stk.push((0, 0, 0));
        while stk.len() > 0 {
            let l = stk.last_mut().unwrap();
            let node = l.0 as usize;
            let index = l.1 as usize;
            let depth = l.2;
            if self.first_entry[node] == u32::MAX {
                self.first_entry[node] = self.depths.len() as u32;
            }
            self.depths.push(l.2);
            self.depth_nodes.push(l.0);
            if index >= self.downlink[node].len() {
                _ = stk.pop();
            } else {
                l.1 += 1;
                stk.push((self.downlink[node][index].0, 0, depth + 1));
            }
        }
    }

    fn build_rmq(&mut self) {
        let mut width = 1_usize;
        let dlen = self.depths.len();
        self.rmq_idx.push((0..dlen as u32).collect::<Vec<u32>>());
        loop {
            let newwidth = width * 2;
            if newwidth > dlen {
                break;
            }

            let prev = self.rmq_idx.last().unwrap();
            let mut cur: Vec<u32> = Vec::new();
            for i in 0..dlen {
                let mut idx = prev[i];
                if i + width < dlen && self.depths[prev[i+width] as usize] 
				< self.depths[idx as usize] {
                    idx = prev[i+width];
                }
                cur.push(idx);
            }
            self.rmq_idx.push(cur);
            width = newwidth;
        }
    }

    fn query_rmq(&self, from: usize, to: usize) -> usize {
        let width = to - from + 1;
        if width == 1 {
            self.rmq_idx[0][from] as usize
        } else if width == 2 {
            self.rmq_idx[1][from] as usize
        } else {
            let mut p2 = width.next_power_of_two();
            if width == p2 {
                let idx = p2.trailing_zeros();
                self.rmq_idx[idx as usize][from] as usize
            } else {
                let idx = p2.trailing_zeros() - 1;
                p2 >>= 1;
                let mut minidx = self.rmq_idx[idx as usize][from] as usize;
                let otheridx = self.rmq_idx[idx as usize][to + 1 - p2] as usize;
                if self.depths[otheridx] < self.depths[minidx] {
                    minidx = otheridx;
                }
                minidx
            }
        }
    }

    fn query_lca(&self, node1: u32, node2: u32) -> u32 {
        let left = std::cmp::min(self.first_entry[node1 as usize],
		self.first_entry[node2 as usize]);
        let right = std::cmp::max(self.first_entry[node1 as usize],
		self.first_entry[node2 as usize]);
        let idx = self.query_rmq(left as usize, right as usize);
        self.depth_nodes[idx]
    }

    fn collect_mutations(&self, mut from: u32, to: u32, out: &mut Vec<u32>) {
        while from != to {
            out.push(self.uplink[from as usize].1);
            assert!(self.uplink[from as usize].0 != from);
            from = self.uplink[from as usize].0;
        }
    }

    fn calc_common(&self, mutts: &mut Vec<u32>) -> u32 {
        if mutts.len() == 0 {
            return self.m as u32;
        }
        mutts.sort_unstable();
        mutts.dedup();
        let mut longest = mutts[0];
        for i in 1..mutts.len() {
            longest = std::cmp::max(longest, mutts[i]-mutts[i-1]-1);
        }
        std::cmp::max(longest, self.m as u32 -*mutts.last().unwrap()-1)
    }

    fn find_common(&self, n1: u32, n2: u32) -> u32 {
        if n1 == n2{
            return self.m as u32;
        }
        let lca = self.query_lca(n1, n2);
        let mut mutts = vec![];
        if lca == n1 {
            self.collect_mutations(n2, lca, &mut mutts);
        } else if lca == n2 {
            self.collect_mutations(n1, lca, &mut mutts);
        } else {
            self.collect_mutations(n1, lca, &mut mutts);
            self.collect_mutations(n2, lca, &mut mutts);
        }
        self.calc_common(&mut mutts)
    }
}

fn main() -> Result<(), Box<dyn Error>> {
    let mut buf = String::new();
    _ = std::io::stdin().read_line(&mut buf)?;
    let mut iter = buf.split_ascii_whitespace();
    let m = iter.next().ok_or("")?.parse::<usize>()?;
    let n = iter.next().ok_or("")?.parse::<usize>()?;
    let k = iter.next().ok_or("")?.parse::<usize>()?;
    let mut uplink: Vec<(u32,u32)> = vec![(0, 0); n];
    let mut downlink: Vec<Vec<(u32, u32)>> = vec![vec![]; n];
    for _ in 0..n-1 {
        buf.clear();
        _ = std::io::stdin().read_line(&mut buf)?;
        let mut iter = buf.split_ascii_whitespace();
        let s = iter.next().ok_or("")?.parse::<u32>()?;
        let d = iter.next().ok_or("")?.parse::<u32>()?;
        let b = iter.next().ok_or("")?.parse::<u32>()?;
        uplink[d as usize - 1] = (s - 1, b);
        downlink[s as usize -1].push((d - 1, b));
    }

    let mut st = State::new(n, m, uplink, downlink);
    st.make_depths();
    st.build_rmq();

    //println!("depths: {:?}", st.depths);
    //println!("depth_nodes: {:?}", st.depth_nodes);
    //println!("rmq: {:?}", st.rmq_idx);

    for _ in 0..k {
        buf.clear();
        _ = std::io::stdin().read_line(&mut buf)?;
        let mut iter = buf.split_ascii_whitespace();
        let p = iter.next().ok_or("")?.parse::<u32>()?;
        let q = iter.next().ok_or("")?.parse::<u32>()?;
        println!("{}", st.find_common(p-1, q-1));
    }
    
    Ok(())
}
\end{verbatim}
\end{document}