Паша и Аким составляли карту леса — полянки были вершинами графа, а дорожки, соединяющие полянки, были рёбрами. Они решили зашифровать количество смешливых грибов на каждой полянке следующим образом — на каждом ребре между двумя полянками они написали два числа — наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) количества грибов на этих полянках. Но однажды Паша и Аким поссорились из-за смешливых грибов и порвали карту. У Паши осталась лишь какая-то часть, на которой было всего лишь m тропинок. Ваша задача — помочь Паше восстановить по карте, которая у него есть, сколько грибов было на каждой полянке. Так как ответ не обязательно однозначный, восстановите любой, либо сообщите, что такого расположения грибов не существует. Гарантируется, что на изначальной карте числа на дорожках были не меньше 1 и не больше 106.
Выходные данные
Выведите в первой строке "NO" если расставить числа невозможно. Иначе выведите "YES", а в следующей строчке выведите n чисел — количество грибов на соответствующей полянке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 0
|
YES
1
|
|
2
|
2 1
1 2 1 3
|
YES
1 3
|
|
3
|
3 2
3 2 1 2
3 1 1 10
|
YES
5 1 2
|
|
4
|
2 1
1 2 3 7
|
NO
|