Сложность: 67%
Очередные сборы по спортивному программированию обернулись проблемой: оказалось, что ребята разделились на враждующие между собой гильдию питонистов и гильдию сипипишников. Вы провели с ними воспитательную беседу и решили поступить так: ученики разобьются на пары, где будет один человек от питонистов и один от сипипишников. Поскольку у ребят разный уровень социализации, может получиться так, что кто-то не нашёл себе ни одной пары, а кто-то вступил сразу в несколько. Гарантируется, что все пары уникальны.
Вы должны выдать каждой паре какую-нибудь задачку. Конечно, можно давать одну и ту же задачу разным парам. Однако, чтобы никому не было скучно, нельзя допустить ситуацию, что один и тот же человек дважды встретится с одной и той же задачей.
Авторы задач знают, какой это тяжкий труд – придумывать задачки. Поэтому от вас требуется минимизировать количество выданных задач.
Входные данные
В первой строке записаны три числа , и – количество питонистов, количество сипипишников и количество образованных между ними пар. (, )
В следующих строках записано по два числа и , которые означают, что между питонистом под номером и сипипишником образована пара.
Выходные данные
Обозначим искомое минимальное число задач как . В этой задаче у вас есть два формата вывода на выбор:
Если вы знаете только число :
В первой строке выведите noob
, а во второй - число .
Если вы знаете число , а так же задачу под каким номером стоит дать каждой паре:
В первой строке выведите tourist
, во второй - число , в третьей – чисел через пробел, где -тое число находится в диапазоне от до включительно и означает номер задачи, которую стоит дать -той паре по порядку представления во входных данных.
Если решений несколько, выведите любое.
Система оценки
Если при проверке подзадачи ваше решение хотя бы один раз выведет ответ в формате noob
, то за эту подзадачу вы получите лишь 30% баллов.
Подзадачи
№ | баллы | необх. подзадачи | ограничения |
1 | 10 | - | |
2 | 40 | 1 | |
3 | 50 | 1, 2 | Нет дополнительных ограничений |
STDIN | STDOUT |
3 3 5 3 1 1 1 2 2 2 1 3 2 | tourist 3 3 2 2 1 1 |
3 3 5 3 1 1 1 2 2 2 1 3 2 | noob 3 |