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 MOD = 1e9 + 7;
template <typename T>
void chmin(T &a, T b) {
  if (a > b) a = b;
}
template <typename T>
void chmax(T &a, T b) {
  if (a < b) a = b;
}
template <typename T>
void add(T &a, T b) {
  a += b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
}
void FastIn(int &T) {
  char C;
  bool F = 0;
  for (; C = getchar(), C < '0' || C > '9';)
    if (C == '-') F = 1;
  for (T = C - '0'; C = getchar(), C >= '0' && C <= '9'; T = T * 10 + C - '0')
    ;
  F && (T = -T);
}
int in() {
  int x;
  scanf("%d", &x);
  return x;
}
long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
double din() {
  double x;
  scanf("%lf", &x);
  return x;
}
long long p2[63];
void initP2() {
  p2[0] = 1;
  for (int i = (1); i <= (62); ++i) {
    p2[i] = p2[i - 1] * 2;
  }
}
int countBitsBaseB(long long n, long long b) {
  if (n == 0) return 1;
  int ret = 0;
  while (n) {
    ret++;
    n /= b;
  }
  return ret;
}
int count1(long long n) {
  int ret = 0;
  while (n) {
    ret += n & 1;
    n >>= 1;
  }
  return ret;
}
long long c[1024][1024] = {0};
void initC() {
  for (int i = 0; i < (1024); ++i) {
    for (int j = 0; j < (i + 1); ++j) {
      if (j == 0 || j == i) {
        c[i][j] = 1;
      } else {
        c[i][j] = c[i - 1][j - 1];
        add(c[i][j], c[i - 1][j]);
      }
    }
  }
}
bool IsPrime(int n) {
  if (n < 2) return false;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void init() {
  initP2();
  initC();
}
const unsigned INVALID = 2000000001;
vector<int> edges[(int)(2e5 + 10)];
int visited[(int)(2e5 + 10)];
vector<pair<int, int>> ps;
bool DFS(int r) {
  visited[r] = 1;
  for (auto v : edges[r]) {
    if (visited[v] == 1) {
      return true;
    }
  }
  for (auto v : edges[r]) {
    if (visited[v] == 0) {
      if (DFS(v)) {
        return true;
      }
    }
  }
  visited[r] = 2;
  return false;
}
int main() {
  init();
  int n = in(), m = in();
  for (int i = (1); i <= (n); ++i) {
    edges[i].clear();
  }
  ps.clear();
  for (int i = 0; i < (m); ++i) {
    int x = in(), y = in();
    edges[x].push_back(y);
    ps.push_back(make_pair(x, y));
  }
  memset((visited), (0), sizeof((visited)));
  bool cycle = false;
  for (int i = (1); i <= (n); ++i) {
    if (visited[i] == 0) {
      if (DFS(i)) {
        cycle = true;
      }
    }
  }
  if (!cycle) {
    puts("1");
    for (int i = 0; i < (m); ++i) {
      printf("1 ");
    }
  } else {
    puts("2");
    for (int i = 0; i < (m); ++i) {
      printf("%d ", (ps[i].first > ps[i].second) + 1);
    }
  }
  return 0;
}