Classification of Vertices in a Directed Graph

You are given a simple directed graph \(G\) with \(n\) vertices and \(m\) edges. The vertices are numbered from \(1\) to \(n\). A simple directed graph is defined as a directed graph with no multiple edges and no self-loops.

A vertex \(r\) is called a root of \(G\) if for every vertex \(k\) (\(1 \le k \le n\)) there exists exactly one simple directed path from \(r\) to \(k\). A simple path is one that does not visit any vertex more than once.

The vertices are classified into three types:

1. If vertex \(r\) is a root of \(G\) (i.e. in \(G\) there is exactly one simple path from \(r\) to every vertex), then it is called a first-type vertex.
2. If vertex \(r\) is not a first-type vertex, but there exists a way to delete some edges from \(G\) to obtain a subgraph \(G'\) such that all of the first-type vertices of \(G\) remain roots in \(G'\) and furthermore \(r\) becomes a root of \(G'\), then \(r\) is called a second-type vertex.
3. If \(r\) does not satisfy any of the above conditions, it is called a third-type vertex.

It is guaranteed that every vertex of \(G\) belongs to exactly one of the three types. Your task is to determine the type for each vertex \(1, 2, \dots, n\). Output 1 for a first-type vertex, 2 for a second-type vertex, and 3 for a third-type vertex.

Note: A vertex \(r\) is a root of \(G\) if and only if the following holds in \(G\): \[ \begin{cases} \text{For } r: 1 \text{ (the trivial path)},\\ \text{For every } k \neq r: \text{exactly one simple path from } r \text{ to } k. \end{cases} \]

A spanning arborescence (directed tree) is a special case where \(m = n-1\) and there is exactly one vertex (the root) with no incoming edges and every other vertex has exactly one incoming edge; moreover, the graph is acyclic and every vertex is reachable from the root. In this case, the unique root is a first-type vertex and every other vertex is considered third-type.

inputFormat

The first line contains two integers \(n\) and \(m\) — the number of vertices and edges of the graph \(G\), respectively.

The next \(m\) lines each contain two integers \(u\) and \(v\), representing a directed edge from vertex \(u\) to vertex \(v\).

outputFormat

Output a single line containing \(n\) integers. The \(i\)th integer should be:

• 1 if vertex \(i\) is a first-type vertex,
• 2 if vertex \(i\) is a second-type vertex,
• 3 if vertex \(i\) is a third-type vertex.

sample

3 2
1 2
2 3

1 3 3