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;
vector<pair<int, int> > sides;
vector<int> ans;
class node {
 public:
  char color;
  int d;
  int index;
  node* parent;
  node() {
    color = 'w';
    d = 10000;
    parent = NULL;
    index = -1;
  }
};
int find(int a, int b) {
  pair<int, int> temp = make_pair(a, b);
  for (int i = 0; i < sides.size(); i++) {
    if (sides[i] == temp) return i;
  }
  return -1;
}
class Graph {
  int V;
  list<int>* adj;
  bool isCyclicUtil(int v, bool visited[], bool* rs);

 public:
  Graph(int V);
  void addEdge(int v, int w);
  bool isCyclic();
};
Graph::Graph(int V) {
  this->V = V;
  adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) { adj[v].push_back(w); }
bool Graph::isCyclicUtil(int v, bool visited[], bool* recStack) {
  if (visited[v] == false) {
    visited[v] = true;
    recStack[v] = true;
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i) {
      if (!visited[*i] && isCyclicUtil(*i, visited, recStack))
        return true;
      else if (recStack[*i])
        return true;
    }
  }
  recStack[v] = false;
  return false;
}
bool Graph::isCyclic() {
  bool* visited = new bool[V];
  bool* recStack = new bool[V];
  for (int i = 0; i < V; i++) {
    visited[i] = false;
    recStack[i] = false;
  }
  for (int i = 0; i < V; i++)
    if (isCyclicUtil(i, visited, recStack)) return true;
  return false;
}
void bfs(int check, node* vertices, vector<node*>* edges) {
  vertices[check].d = 0;
  list<int> yo;
  yo.push_back(check);
  int u;
  while (!yo.empty()) {
    u = yo.front();
    yo.pop_front();
    for (int i = 0; i < edges[u].size(); i++) {
      if (edges[u][i]->color == 'w') {
        edges[u][i]->color = 'g';
        edges[u][i]->d = vertices[u].d + 1;
        edges[u][i]->parent = &vertices[u];
        yo.push_back(edges[u][i]->index);
      } else if (edges[u][i]->color == 'b') {
        int index = find(u, edges[u][i]->index);
        ans[index] = 2;
      }
    }
    vertices[u].color = 'b';
  }
}
void path(int i, int s, node vertices[]) {
  if (i == s)
    cout << s << ' ';
  else {
    path(vertices[i].parent->index, s, vertices);
    cout << i << ' ';
  }
}
int main() {
  int v, e;
  cin >> v >> e;
  pair<int, int> temp;
  Graph g(v);
  node* vertices = new node[v];
  for (int i = 0; i < v; i++) vertices[i].index = i;
  vector<node*>* edges = new vector<node*>[v];
  for (int i = 0; i < e; i++) {
    cin >> temp.first >> temp.second;
    edges[--temp.first].push_back(&vertices[--temp.second]);
    g.addEdge(temp.first, temp.second);
    sides.push_back(temp);
    ans.push_back(1);
  }
  if (!g.isCyclic()) {
    cout << 1 << endl;
    for (int i = 0; i < e; i++) {
      cout << 1 << ' ';
    }
    return 0;
  }
  for (int i = 0; i < v; i++) {
    if (vertices[i].color == 'w') {
      bfs(i, vertices, edges);
    }
  }
  cout << 2 << endl;
  for (int i = 0; i < e; i++) {
    cout << ans[i] << ' ';
  }
}