This problem has nothing to do with problem A
Danna is the owner of "Dulce Alfajor", a renowned traditional Argentine sweets company. Due to her immense success, her factory has expanded into a massive complex with strict safety protocols.
The factory layout can be modeled as a directed acyclic graph with $$$n + 1$$$ rooms and $$$m$$$ directed halls, numbered from $$$0$$$ to $$$n$$$. Room $$$0$$$ is the main entrance, while rooms $$$1$$$ through $$$n$$$ are covered in sticky candy and need to be cleaned.
Danna needs to assign a color preference $$$C_i$$$ to each room $$$i$$$ ($$$1 \le i \le n$$$) each room needs to have one asigned color. She will then hire exactly one worker for each unique color used. The cleaning process operates under the following rules:
- Room $$$0$$$ contains all colors, so any worker can start their cleaning route there.
- Each worker is assigned a specific color $$$c$$$ and will only enter and clean rooms assigned color $$$c$$$.
- A worker assigned color $$$C_w$$$ starts at room $$$0$$$ and traverses a directed path $$$0 \to v_1 \to v_2 \to \dots \to v_m$$$ where for every room ($$$1 \lt = j \lt = m$$$) the color is the same as the color of the worker ($$$C_w = C_{v_j}$$$), cleaning every room along that path.
- Every room assigned color $$$c$$$ must be visited at least once and cleaned by that worker in a single route.
- Every room from $$$1$$$ to $$$n$$$ must be visited and cleaned by exactly one worker.
- Workers will always choose the path that maximizes the amount of rooms they can clean
It is guaranteed that there is a direct corridor from Room $$$0$$$ to every room $$$v \in [1, n]$$$, and no room $$$v \in [1, n]$$$ has a corridor leading to Room $$$0$$$.
Note that a worker can visit a room even if it has already been cleaned.
Help Danna determine the minimum number of unique colors $$$K$$$ required to clean the entire factory, and output a valid color assignment $$$C_1, C_2, \dots, C_n$$$ ($$$1 \le C_i \le K$$$) for rooms $$$1$$$ through $$$n$$$.
The first line contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n \le m \le n + 2 \cdot 10^5$$$) — the number of candy-covered rooms (excluding room $$$0$$$) and the number of directed halls between rooms $$$0$$$ through $$$n$$$, respectively.
Each of the next $$$m$$$ lines contains two space-separated integers $$$u_i$$$ and $$$v_i$$$ ($$$0 \le u_i \le n$$$, $$$1 \le v_i \le n$$$, $$$u_i \neq v_i$$$), representing a directed hall from room $$$u_i$$$ to room $$$v_i$$$. It's guaranteed that there exist a directed hall from room 0 to every other room and there are no multiple edges.
On the first line, print a single integer $$$K$$$ ($$$1 \le K \le n$$$) — the minimum number of unique colors required to clean all rooms.
On the second line, print $$$n$$$ space-separated integers $$$C_1, C_2, \dots, C_n$$$ ($$$1 \le C_i \le K$$$), where $$$C_i$$$ represents the color assigned to room $$$i$$$.
If there are multiple valid color assignments using $$$K$$$ colors, you may print any of them.
1 10 1
1 1
5 80 10 20 30 40 51 22 43 5
2 1 1 2 1 2
5 80 10 20 30 40 51 22 43 4
3 1 1 2 1 3
