Есть дерево из \(n\) вершин, в котором живут \(m\) муравьёв. Каждый муравей имеет свой собственный цвет. У \(i\)-го муравья есть две любимые пары вершин: (\(a_i, b_i\)) и (\(c_i, d_i\)). Вам нужно сказать, можно ли раскрасить рёбра дерева в \(m\) цветов так, чтобы каждый муравей мог ходить между вершинами какой-то из своих любимых пар, используя только рёбра своего цвета; и если можно, то вывести, какую из пар будет использовать каждый муравей.
Выходные данные
Выведите «NO» (без кавычек), если искомая раскраска рёбер невозможна.
Иначе выведите «YES» (без кавычек). В \(i\)-й из \(m\) следующих строк выведите \(1\), если \(i\)-й муравей будет использовать первую пару, и \(2\) иначе. Если существует несколько решений, выведите любое из них.
Примечание
В примере второе и третье ребро следует покрасить в первый цвет, первое и пятое — во второй цвет, а четвёртое — в третий цвет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2
3 1
4 1
5 2
6 2
3
2 6 3 4
1 6 6 5
1 4 5 2
|
YES
2
1
2
|
|
2
|
5
1 2
1 3
1 4
1 5
2
2 3 4 5
3 4 5 2
|
NO
|