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;
template <typename Arg, typename... Args>
void trace(Arg &&arg, Args &&...args) {}
inline int ni() {
  int x;
  scanf("%d", &x);
  return x;
}
inline long long nl() {
  long long x;
  scanf("%lld", &x);
  return x;
}
template <typename T>
T min_(T a, T b) {
  return a > b ? b : a;
}
template <typename T, typename... Ts>
T min_(T first, Ts... last) {
  return min_(first, min_(last...));
}
template <typename T>
T max_(T a, T b) {
  return a > b ? a : b;
}
template <typename T, typename... Ts>
T max_(T first, Ts... last) {
  return max_(first, max_(last...));
}
template <class T, class S>
void outvp(vector<pair<T, S>> &v) {
  for (pair<T, S> x : v) cout << x.first << " " << x.second << endl;
}
template <typename T>
void outv(vector<T> &v) {
  for (T x : v) cout << x << " ";
  cout << endl;
}
template <typename T>
void outs(set<T> &v) {
  for (T x : v) cout << x << " ";
  cout << endl;
}
template <typename T>
void outm(map<T, int> &v, int n = 1) {
  for (T &x : v) cout << (n == 1 ? x.first : x.second) << " ";
  cout << endl;
}
template <typename T>
void finalize(T x) {
  cout << x << endl;
  exit(0);
}
void yesno(int x, int last = 1) {
  cout << (x ? "YES" : "NO") << endl;
  if (last) exit(0);
}
template <typename T>
void readv(vector<T> &v, int n) {
  v = vector<T>(n);
  for (int i = 0; i < (int)(n); i++) cin >> (v[i]);
}
template <typename T>
void reads(set<T> &v, int n) {
  T x;
  for (int i = 0; i < (int)(n); i++) {
    cin >> x;
    v.insert(x);
  }
}
template <typename T>
void readm(map<T, int> &v, int n) {
  T x;
  for (int i = 0; i < (int)(n); i++) {
    cin >> x;
    v[x]++;
  }
}
template <typename Arg, typename... Args>
void read(Arg &&arg, Args &&...args) {
  cin >> std::forward<Arg>(arg);
  using expander = int[];
  (void)expander{0, (void(cin >> std::forward<Args>(args)), 0)...};
}
long long pwr(long long base, long long p, long long mod) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a * (b / gcd(a, b)); }
const long double PI = (long double)(3.1415926535897932384626433832795);
const long long mx_ll = numeric_limits<long long>::max();
const int mx_int = numeric_limits<int>::max();
const int mod = 1e9 + 7;
const int oo = 0x3f3f3f3f;
const long long OO = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-9;
const int dx[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
const int dsx[4] = {0, 1, 0, -1};
const int dsy[4] = {1, 0, -1, 0};
const int maxn = 5123;
vector<int> g[maxn];
int ans[maxn];
int vis[maxn];
int k = 1;
map<pair<int, int>, int> od;
void _build() {
  memset(vis, 0, sizeof(vis));
  for (int i = 0; i < (int)(maxn); i++) ans[i] = 1;
}
void dfs(int u) {
  vis[u] = 1;
  for (int v : g[u]) {
    if (vis[v] == 1) {
      k = 2;
      ans[od[{u, v}]] = 2;
    } else if (vis[v] == 0) {
      dfs(v);
    }
  }
  vis[u] = 2;
}
void _solve() {
  int n, m;
  read(n, m);
  vector<pair<int, int>> a;
  for (int i = 0; i < (int)(m); i++) {
    int u, v;
    read(u, v);
    u--;
    v--;
    g[u].push_back(v);
    od[{u, v}] = i;
    a.push_back({u, v});
  }
  for (int i = 0; i < (int)(n); i++)
    if (0 == vis[i]) dfs(i);
  cout << k << endl;
  for (int i = 0; i < (int)(m); i++) cout << ans[i] << " ";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  bool GOOGLE = false;
  _build();
  int qq = 1;
  if (GOOGLE) cin >> qq;
  for (int i = 0; i < (int)(qq); i++) {
    if (GOOGLE) cout << "Case #" << i + 1 << ": ";
    _solve();
  }
}