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