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 INF = 1LL << 60;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
long long modpow(long long a, long long n, long long mod) {
  long long res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}
struct Edge {
  int u, v, color;
  Edge(int u, int v, int color) : u(u), v(v), color(color) {}
};
constexpr int MAX_N = 5100;
vector<int> G[MAX_N];
vector<Edge> edges;
int n, m, k = 1;
vector<int> topo_sort() {
  vector<int> indeg(n);
  set<int> st;
  for (int i = int(0); i < int(n); ++i) {
    indeg[i] = 0;
  }
  for (int i = int(0); i < int(n); ++i) {
    for (int to : G[i]) {
      indeg[to]++;
    }
  }
  for (int i = int(0); i < int(n); ++i) {
    if (indeg[i] == 0) {
      st.insert(i);
    }
  }
  vector<int> ret;
  vector<int> used(n);
  for (int i = int(0); i < int(n); ++i) used[i] = 0;
  while (!st.empty()) {
    int node = *st.begin();
    st.erase(node);
    ret.push_back(node);
    used[node];
    for (int next : G[node]) {
      --indeg[next];
      if (!used[next] && indeg[next] == 0) st.insert(next);
    }
  }
  return ret;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  int u, v;
  for (int i = int(0); i < int(m); ++i) {
    cin >> u >> v;
    u--;
    v--;
    edges.push_back(Edge(u, v, 1));
    G[u].push_back(v);
  }
  vector<int> ordered_nodes = topo_sort();
  vector<int> c(m, 1);
  if (ordered_nodes.size() == n) {
    k = 1;
  } else {
    k = 2;
    for (int i = int(0); i < int(m); ++i) {
      if (edges[i].u > edges[i].v) c[i] = 2;
    }
  }
  cout << k << endl;
  for (int i = int(0); i < int(m); ++i) {
    cout << c[i] << " ";
  }
  cout << endl;
  return 0;
}