← К соревнованиям

Sort Me Round

Помирить всех

Сложность: 67%

Очередные сборы по спортивному программированию обернулись проблемой: оказалось, что ребята разделились на враждующие между собой гильдию питонистов и гильдию сипипишников. Вы провели с ними воспитательную беседу и решили поступить так: ученики разобьются на пары, где будет один человек от питонистов и один от сипипишников. Поскольку у ребят разный уровень социализации, может получиться так, что кто-то не нашёл себе ни одной пары, а кто-то вступил сразу в несколько. Гарантируется, что все пары уникальны.

Вы должны выдать каждой паре какую-нибудь задачку. Конечно, можно давать одну и ту же задачу разным парам. Однако, чтобы никому не было скучно, нельзя допустить ситуацию, что один и тот же человек дважды встретится с одной и той же задачей.

Авторы задач знают, какой это тяжкий труд – придумывать задачки. Поэтому от вас требуется минимизировать количество выданных задач.

Входные данные

В первой строке записаны три числа n1n_1, n2n_2 и mm – количество питонистов, количество сипипишников и количество образованных между ними пар. (1n1,n2<n1+n230001 \le n_1, n_2 < n_1 + n_2 \le 3000, 0m1050 \le m \le 10^5)

В следующих mm строках записано по два числа aia_i и bib_i, которые означают, что между питонистом под номером aia_i и сипипишником bib_i образована пара.

Выходные данные

Обозначим искомое минимальное число задач как tt. В этой задаче у вас есть два формата вывода на выбор:

  • Если вы знаете только число tt:

    В первой строке выведите noob, а во второй - число tt.

  • Если вы знаете число tt, а так же задачу под каким номером стоит дать каждой паре:

    В первой строке выведите tourist, во второй - число tt, в третьей – mm чисел через пробел, где ii-тое число находится в диапазоне от 11 до tt включительно и означает номер задачи, которую стоит дать ii-той паре по порядку представления во входных данных.

    Если решений несколько, выведите любое.

Система оценки

Если при проверке подзадачи ваше решение хотя бы один раз выведет ответ в формате noob, то за эту подзадачу вы получите лишь 30% баллов.

Подзадачи

баллынеобх. подзадачиограничения
1

10

-

(n1+n2)10(n_1 + n_2) \le 10

2

40

1

m2500m \le 2500

3

50

1, 2

Нет дополнительных ограничений

STDINSTDOUT
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