|
Тапкодер
(Время: 3 сек. Память: 16 Мб Сложность: 78%)
Ассоциация Тапкодер организует Всемирное парное соревнование сильнейших программистов. К участию в соревновании допущены первые 2K зарегистрировавшихся участников, которым присвоены номера от 1 до 2K.
Соревнование будет проходить по олимпийской системе. В первом туре первый участник встречается со вторым, третий с четвертым и так далее. В каждой паре победителем становится участник, первым решивший предложенную задачу, при этом ничьих не бывает. Все победители очередного тура и только они являются участниками следующего тура. В каждом туре пары составляются из участников в порядке возрастания присвоенных им номеров. Соревнование продолжается до тех пор, пока не останется один победитель.
Организаторам стало известно, что некоторые пары участников заранее договорились о результате встречи между собой, если такая встреча состоится. Для всех остальных встреч, кроме N договорных, возможен любой исход.
Некоторые M участников соревнования представили свои резюме в ассоциацию Тапкодер с целью поступления на работу. Организаторов интересует, до какого тура может дойти каждый из претендентов при наиболее благоприятном для него стечении обстоятельств. При этом для каждого участника в отдельности считается, что все недоговорные встречи, в том числе те, в которых он не участвует, закончатся так, как ему выгодно, а все состоявшиеся договорные встречи закончатся в соответствии с имеющимися договоренностями.
Требуется написать программу, которая для каждого из претендентов определяет максимальный номер тура, в котором он может участвовать.
Входные данные
В первой строке входного файла INPUT.TXT заданы три целых числа K (1 ≤ K ≤ 60), N (0 ≤ N ≤ 100 000) и M (1 ≤ M ≤ 100 000). В следующих N строках описаны N пар участников, которые договорились между собой о том, что первый из двух участников пары выиграет встречу, если она состоится. Гарантируется, что каждая пара участников присутствует во входных данных не более одного раза, при этом, если задана пара X Y, то пары Y X быть не может, кроме того, X ≠ Y. В последней строке файла перечислены номера участников, желающих работать в Тапкодере, в порядке возрастания их номеров. Все номера претендентов на работу различны.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать M целых чисел — максимальные номера туров, до которых могут дойти соответствующие претенденты на работу. Туры нумеруются от 1 до K.
Примеры
| № | INPUT.TXT | OUTPUT.TXT | Комментарий |
|---|
| 1 | 2 0 3
1 3 4 | 2 2 2 | У каждого из участников есть возможность выйти в финал, так как договорных матчей нет |
| 2 | 3 1 1
3 1
1 | 3 | Если четвертый участник выиграет у третьего, то договорная встреча первого и третьего не состоится, что благоприятно для первого |
| 3 | 3 3 4
1 2
1 3
4 1
1 2 3 4
| 3 1 2 3 | Первому участнику благоприятно во втором туре играть с третьим, а не с четвертым, в свою очередь, четвертый может выиграть у третьего и также выйти в финал |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
