Problem: You are given a directed graph with n vertices and m directed edges without self-loops or multiple edges.

Let's denote the k-coloring of a digraph as following: you color each edge in one of k colors. The k-coloring is good if and only if there no cycle formed by edges of same color.

Find a good k-coloring of given digraph with minimum possible k.

Input

The first line contains two integers n and m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 5000) — the number of vertices and edges in the digraph, respectively.

Next m lines contain description of edges — one per line. Each edge is a pair of integers u and v (1 ≤ u, v ≤ n, u ≠ v) — there is directed edge from u to v in the graph.

It is guaranteed that each ordered pair (u, v) appears in the list of edges at most once.

Output

In the first line print single integer k — the number of used colors in a good k-coloring of given graph.

In the second line print m integers c_1, c_2, ..., c_m (1 ≤ c_i ≤ k), where c_i is a color of the i-th edge (in order as they are given in the input).

If there are multiple answers print any of them (you still have to minimize k).

Examples

Input


4 5
1 2
1 3
3 4
2 4
1 4


Output


1
1 1 1 1 1 


Input


3 3
1 2
2 3
3 1


Output


2
1 1 2 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long MOD = 1000000007;
long long gcd(long long a, long long b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
class matrix {
 public:
  int row, col;
  vector<vector<long long> > num;
  matrix(int r, int c, int val) {
    this->num = vector<vector<long long> >(r, vector<long long>(c, val));
    this->row = r;
    this->col = c;
  }
  matrix(vector<vector<long long> > mtx) {
    this->num = mtx;
    this->row = mtx.size();
    this->col = mtx[0].size();
  }
  matrix operator*(matrix another) {
    matrix newone(this->row, another.col, INT_MIN);
    for (int r = 0; r < newone.row; r++) {
      for (int c = 0; c < newone.col; c++) {
        for (int k = 0; k < this->col; k++) {
          newone.num[r][c] += this->num[r][k] * another.num[k][c];
          newone.num[r][c] %= MOD;
        }
      }
    }
    return newone;
  }
  matrix operator^(long long x) {
    if (x == 1)
      return *this;
    else {
      matrix halfpower = (*this) ^ (x / 2);
      if (x % 2 == 0)
        return halfpower * halfpower;
      else
        return halfpower * halfpower * (*this);
    }
  }
};
int n, m, fm[5005], to[5005], t, in[5005], out[5005], vsted[5005], ans[5005];
vector<int> v[5005];
void dfs(int s) {
  vsted[s] = 1;
  in[s] = t;
  t++;
  int sz = v[s].size();
  for (int i = 0; i < sz; i++)
    if (!vsted[v[s][i]]) dfs(v[s][i]);
  out[s] = t;
  t++;
}
bool isback(int u, int v) {
  if ((in[v] < in[u]) && (out[u] < out[v]))
    return true;
  else
    return false;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &fm[i], &to[i]);
    v[fm[i]].push_back(to[i]);
  }
  for (int i = 1; i <= n; i++)
    if (!vsted[i]) dfs(i);
  bool hascycle = false;
  for (int i = 0; i < m; i++) {
    if (isback(fm[i], to[i]))
      hascycle = true, ans[i] = 2;
    else
      ans[i] = 1;
  }
  printf("%d\n", hascycle ? 2 : 1);
  for (int i = 0; i < m; i++) printf("%d ", ans[i]);
  return 0;
}