В \(31\) лицее существовало две группы олимпиадников: информатики и математики. Численность информатиков составляла \(n_1\), математиков — \(n_2\). Точно неизвестно кто какой именно группе принадлежал, но известно, что между некоторыми парами людей существовали дружественные связи (причем они могли образовываться как между парой людей одной группы, так и двух различных).
Связи были настолько крепкими, что даже если убрать одного человека, а вместе с ним убрать все его дружественные связи, то любая пара людей всё равно оставалась знакома либо напрямую, либо через общих приятелей.
\(^{\dagger}\) Более формально, два человека \((x, y)\) знакомы в следующем случае: найдутся такие люди \(a_1, a_2, \ldots,a_n\) (\(1 \le a_i \le n_1 + n_2\)), что одновременно выполняются следующие условия:
\(\bullet\) Человек \(x\) напрямую знаком с \(a_1\).
\(\bullet\) Человек \(a_n\) напрямую знаком с \(y\).
\(\bullet\) Человек \(a_i\) напрямую знаком с \(a_{i + 1}\) для любого (\(1 \le i \le n - 1\)).
Преподаватели были недовольны тем, что информатики дружат с математиками и наоборот, и поэтому они решили разделить школьников на две группы таким образом, чтобы выполнялось два условия:
\(\bullet\) В группе информатиков было \(n_1\) человек, а в группе математиков — \(n_2\) человек.
\(\bullet\) Любая пара информатиков должна быть знакома (допускается знакомство при участии общих знакомых, которые обязаны быть из той же группы, что и люди из этой пары), тоже самое должно выполняться и для математиков.
Помогите им разрешить эту задачу и найдите, кто к какой группе относится.
Выходные данные
Для каждого набора входных данных выведите две строки.
В первой строке выведите \(n_1\) различных чисел \(a_i\) (\(1 \le a_i \le n_1 + n_2\)) — люди, принадлежащие первой группе.
Во второй строке выведите \(n_2\) различных чисел \(b_i\) (\(1 \le b_i \le n_1 + n_2\)) — люди, принадлежащие второй группе.
Все числа должны быть различные.
Если существует несколько вариантов ответа, выведите любой.
Примечание
Рассмотрим третий набор входных данных. Разделение на группы выглядит следующим образом:
В зелёный цвет покрашены школьники, которые были выбраны информатиками, в синий же цвет покрашены те, кто были выбраны математиками.
Рассмотрим все пары информатиков и то, как они знакомы:
Пары \((4, 5), (4, 6)\) знакомы напрямую.
Пара \((5, 6)\) знакома через информатика с номером \(4\).
Рассмотрим все пары математиков и то, как они знакомы:
Пары \((1, 2), (2, 3)\) знакомы напрямую.
Пара \((1, 3)\) знакома через математика с номером \(2\).
Получаем, что любая пара людей, принадлежащих одной группе, знакомы друг с другом, а значит разбиение на две группы верное.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
2 3
1 3
1 2
1 4 7
2 5
3 4
2 4
1 2
3 5
4 5
1 5
3 3 7
1 2
1 6
2 3
2 5
3 4
4 5
4 6
|
3
1 2
5
1 2 3 4
4 5 6
1 2 3
|