Magical Plants

문제

John is growing plants on the windowsill. These are no ordinary plants: they are in telepathic communication with one another and will grow only if some other plants are already tall enough.

There are $NN$ pots on the windowsill, numbered $1\dots N1\; \backslash ldots\; N$. Initially there is nothing planted in any of the pots. Also, there are $MM$ constraints of the form "the plant in pot $U_{i}U\_i$ can grow $A_{i}A\_i$ metres tall only if the plant in $V_{i}V\_i$ is already at least $B_{i}B\_i$ metres tall".

Days consist of $N+1N\; +\; 1$ minutes. Each day, the following happens:

1. On the $ii$-th minute (for every $1\le i\le N1\; \backslash le\; i\; \backslash le\; N$): if there is a plant growing in the $ii$-th pot, it will grow 1 metre taller unless that would violate one of the constraints.
2. On the $N+1N\; +\; 1$-st minute: John can choose a pot with no plant in it, and plant a plant there. Initially, a plant is 1 metre tall.

We need each plant to be at least $KK$ metres tall to brew a potion. Find the minimum number of days necessary, assuming John plants the plants optimally. Find one optimal way to plant the plants.

It is guaranteed that in all test cases it is possible to plant the plants so that all plants will grow $KK$ metres tall in at most ${10}^{18}10^\{18\}$ days.

입력

The first line of the input consists of three space-separated integers $NN$, $MM$ and $KK$ ($1\le N,M\le 2\cdot {10}^{5}1\; \backslash le\; N,\; M\; \backslash le\; 2\; \backslash cdot\; 10^5$, $2\le K\le {10}^{9}2\; \backslash le\; K\; \backslash le\; 10^9$).

The next $MM$ lines describe the constraints. The $ii$-th such row consists of four integers $U_{i}U\_i$, $A_{i}A\_i$, $V_{i}V\_i$, $B_{i}B\_i$ ($1\le U_i,V_i\le N1\; \backslash le\; U\_i,\; V\_i\; \backslash le\; N$, $U_i\mathrm{\ne }{V}_{i}U\_i\; \backslash ne\; V\_i$, $2\le A_i,B_i\le K2\; \backslash le\; A\_i,\; B\_i\; \backslash le\; K$), describing a constraint.

출력

The first line of the output must consist of the minimum number of days needed for all plants to grow at least $KK$ metres tall.

The second line must consist of $NN$ integers, each from the interval $1\dots {10}^{9}1\; \backslash ldots\; 10^9$. Of those, the $ii$-th should be the day John plants the $ii$-th plant.

If there are multiple optimal solutions, you can print any one of them.