#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
bool visit[MAXN];
struct node {
  int nxt, gcd, lcm;
  node(int nxt_, int gcd_, int lcm_) {
    nxt = nxt_;
    gcd = gcd_;
    lcm = lcm_;
  }
};
vector<node> e[MAXN];
int n, m;
int a[MAXN], da[MAXN], mx[MAXN];
vector<int> now;
int get_gcd(int x, int y) {
  if (x % y == 0) return y;
  return get_gcd(y, x % y);
}
void dfs(int u) {
  visit[u] = true;
  now.push_back(u);
  for (int i = 0; i < e[u].size(); i++) {
    if (!visit[e[u][i].nxt]) dfs(e[u][i].nxt);
  }
}
bool dfs(int u, int val) {
  a[u] = val;
  for (int i = 0; i < e[u].size(); i++) {
    int v = e[u][i].nxt;
    if (a[v] == 0) {
      int av = (long long)e[u][i].lcm * e[u][i].gcd / a[u];
      if (av == 0) return false;
      if ((long long)a[u] * av != (long long)e[u][i].lcm * e[u][i].gcd)
        return false;
      if (get_gcd(av, a[u]) == e[u][i].gcd) {
        if (!dfs(v, av)) return false;
      } else
        return false;
    } else {
      if (get_gcd(a[v], a[u]) != e[u][i].gcd) return false;
    }
  }
  return true;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) da[i] = 1, mx[i] = 1000000;
  for (int i = 0; i < m; i++) {
    int x, y, gcd, lcm;
    scanf("%d%d%d%d", &x, &y, &gcd, &lcm);
    x--;
    y--;
    e[x].push_back(node(y, gcd, lcm));
    e[y].push_back(node(x, gcd, lcm));
    da[x] = max(da[x], gcd);
    da[y] = max(da[y], gcd);
    mx[x] = min(mx[x], lcm);
    mx[y] = min(mx[y], lcm);
  }
  for (int i = 0; i < n; i++)
    if (!visit[i]) {
      bool flag = false;
      now.clear();
      dfs(i);
      for (int j = da[i]; j <= mx[i]; j += da[i]) {
        for (int k = 0; k < now.size(); k++) a[now[k]] = 0;
        if (dfs(i, j)) {
          flag = true;
          break;
        }
      }
      if (!flag) {
        printf("NO\n");
        return 0;
      }
      for (int k = 0; k < now.size(); k++) visit[now[k]] = true;
    }
  printf("YES\n");
  for (int i = 0; i < n; i++) printf("%d%c", a[i], (i == n - 1) ? '\n' : ' ');
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

Pasha and Akim were making a forest map — the lawns were the graph's vertexes and the roads joining the lawns were its edges. They decided to encode the number of laughy mushrooms on every lawn in the following way: on every edge between two lawns they wrote two numbers, the greatest common divisor (GCD) and the least common multiple (LCM) of the number of mushrooms on these lawns. But one day Pasha and Akim had an argument about the laughy mushrooms and tore the map. Pasha was left with just some part of it, containing only m roads. Your task is to help Pasha — use the map he has to restore the number of mushrooms on every lawn. As the result is not necessarily unique, help Pasha to restore any one or report that such arrangement of mushrooms does not exist. It is guaranteed that the numbers on the roads on the initial map were no less that 1 and did not exceed 106.

Input

The first line contains two numbers n and m (<image>) which are the numbers of lawns and roads we know about. Each of the following m lines contains four numbers which are the numbers of lawns the road connects, the GCD and the LCM of the numbers of mushrooms on these lawns (1 ≤ GCD, LCM ≤ 106).

It is guaranteed, that no road connects lawn to itself, and no two lawns are connected by more than one road.

Output

The answer should contain "YES" or "NO" on the first line, saying whether it is possible or not to perform the arrangement. If the answer is "YES", print on the following line n numbers which are the numbers of mushrooms on the corresponding lawns.

Examples

Input

1 0


Output

YES
1 

Input

2 1
1 2 1 3


Output

YES
1 3 

Input

3 2
3 2 1 2
3 1 1 10


Output

YES
5 1 2 

Input

2 1
1 2 3 7


Output

NO

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
bool visit[MAXN];
struct node {
  int nxt, gcd, lcm;
  node(int nxt_, int gcd_, int lcm_) {
    nxt = nxt_;
    gcd = gcd_;
    lcm = lcm_;
  }
};
vector<node> e[MAXN];
int n, m;
int a[MAXN], da[MAXN], mx[MAXN];
vector<int> now;
int get_gcd(int x, int y) {
  if (x % y == 0) return y;
  return get_gcd(y, x % y);
}
void dfs(int u) {
  visit[u] = true;
  now.push_back(u);
  for (int i = 0; i < e[u].size(); i++) {
    if (!visit[e[u][i].nxt]) dfs(e[u][i].nxt);
  }
}
bool dfs(int u, int val) {
  a[u] = val;
  for (int i = 0; i < e[u].size(); i++) {
    int v = e[u][i].nxt;
    if (a[v] == 0) {
      int av = (long long)e[u][i].lcm * e[u][i].gcd / a[u];
      if (av == 0) return false;
      if ((long long)a[u] * av != (long long)e[u][i].lcm * e[u][i].gcd)
        return false;
      if (get_gcd(av, a[u]) == e[u][i].gcd) {
        if (!dfs(v, av)) return false;
      } else
        return false;
    } else {
      if (get_gcd(a[v], a[u]) != e[u][i].gcd) return false;
    }
  }
  return true;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) da[i] = 1, mx[i] = 1000000;
  for (int i = 0; i < m; i++) {
    int x, y, gcd, lcm;
    scanf("%d%d%d%d", &x, &y, &gcd, &lcm);
    x--;
    y--;
    e[x].push_back(node(y, gcd, lcm));
    e[y].push_back(node(x, gcd, lcm));
    da[x] = max(da[x], gcd);
    da[y] = max(da[y], gcd);
    mx[x] = min(mx[x], lcm);
    mx[y] = min(mx[y], lcm);
  }
  for (int i = 0; i < n; i++)
    if (!visit[i]) {
      bool flag = false;
      now.clear();
      dfs(i);
      for (int j = da[i]; j <= mx[i]; j += da[i]) {
        for (int k = 0; k < now.size(); k++) a[now[k]] = 0;
        if (dfs(i, j)) {
          flag = true;
          break;
        }
      }
      if (!flag) {
        printf("NO\n");
        return 0;
      }
      for (int k = 0; k < now.size(); k++) visit[now[k]] = true;
    }
  printf("YES\n");
  for (int i = 0; i < n; i++) printf("%d%c", a[i], (i == n - 1) ? '\n' : ' ');
  return 0;
}

```