Робот Бендер решил сделать Фраю подарок на день рождения. Он вбил n гвоздей и в определенном порядке пронумеровал их. Робот решил сделать из имеющихся у него железных прутьев картину, представляющую собой замкнутую ломаную, вершинами которой являются гвозди в заданном порядке, а отрезки ломаной параллельны осям координат. Самопересечения допускаются. Бендер может взять подходящий прут, согнуть его ровно один раз в любом месте под углом 90 градусов и прикрепить местом сгиба к еще не занятому гвоздю, а два конца прикрепить к двум соседним. Гвоздь считается незанятым, если к нему не прикреплен ни один прут (ни конец, ни место сгиба). Никакой прут нельзя использовать дважды. Вы можете использовать не все прутья.
Помогите Бендеру решить эту непростую задачу.
Выходные данные
Если задача Бендера неразрешима, выведите NO. Иначе в первой строке выведите YES, а во второй строке выведите n чисел — i-ое число — номер прута, место сгиба которого прикреплена к i-ому гвоздю, или -1, если нет такого прута.
Если решений несколько, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
0 0
0 2
2 2
2 0
4 4
|
YES
1 -1 2 -1
|
|
2
|
6 3
0 0
1 0
1 1
2 1
2 2
0 2
3 2 3
|
YES
1 -1 2 -1 3 -1
|
|
3
|
6 3
0 0
1 0
1 1
2 1
2 2
0 2
2 2 3
|
NO
|