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;
const long long maxn = 500005;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const long long MOD = 100000007;
const double eps = 1e-10;
long long qpow(long long a, long long b) {
  long long tmp = a % MOD, ans = 1;
  while (b) {
    if (b & 1) {
      ans *= tmp, ans %= MOD;
    }
    tmp *= tmp, tmp %= MOD, b >>= 1;
  }
  return ans;
}
long long lowbit(long long x) { return x & -x; }
long long max(long long a, long long b) { return a > b ? a : b; }
long long min(long long a, long long b) { return a < b ? a : b; }
long long mmax(long long a, long long b, long long c) {
  return max(a, max(b, c));
}
long long mmin(long long a, long long b, long long c) {
  return min(a, min(b, c));
}
void mod(long long &a) {
  a += MOD;
  a %= MOD;
}
bool chk(long long now) {}
long long half(long long l, long long r) {
  while (l <= r) {
    long long m = (l + r) / 2;
    if (chk(m))
      r = m - 1;
    else
      l = m + 1;
  }
  return l;
}
long long ll(long long p) { return p << 1; }
long long rr(long long p) { return p << 1 | 1; }
long long mm(long long l, long long r) { return (l + r) / 2; }
long long lg(long long x) {
  if (x == 0) return 1;
  return (long long)log2(x) + 1;
}
bool smleql(double a, double b) {
  if (a < b || fabs(a - b) <= eps) return true;
  return false;
}
double len(double a, double b, double c, double d) {
  return sqrt((a - c) * (a - c) + (b - d) * (b - d));
}
bool isp(long long x) {
  if (x == 1) return false;
  if (x == 2) return true;
  for (long long i = 2; i * i <= x; ++i)
    if (x % i == 0) return false;
  return true;
}
long long n, m, k = 1;
long long x[maxn], y[maxn];
long long p[5005][5005];
long long ans[maxn];
long long v[maxn];
void dfs(long long x, long long f) {
  if (v[x] == 2) {
    p[f][x] = 2;
    return;
  }
  v[x] = 2;
  for (long long i = 1; i <= n; ++i) {
    if (p[x][i] != 0) {
      long long y = i;
      if (v[y] == 0)
        dfs(y, x);
      else if (v[y] == 2)
        k = 2, p[x][y] = 2;
    }
  }
  v[x] = 1;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (long long i = 1; i <= m; ++i) cin >> x[i] >> y[i], p[x[i]][y[i]] = 1;
  for (long long i = 1; i <= n; ++i)
    if (v[i] == 0) dfs(i, 0);
  cout << k << endl;
  for (long long i = 1; i <= m; ++i) cout << p[x[i]][y[i]] << ' ';
  return 0;
}