P7351 “MCOI-04” Dream SMP

**This is an output-only problem.** Link: https://pan.baidu.com/s/1D3ytb0626EKZ_emw3gLwVQ Extraction code: inbj

Dream SMP can be seen as $n$ regions numbered $0,1,\dots,n-1$. Dream wants to divide these $n$ regions into $8$ countries numbered $0,1,\dots,7$. Each region belongs to exactly one country, but a country may contain no regions. The regions give $m$ sets of constraints on the partition plan. The $i$-th constraint is represented by four parameters $(u_i,a_i,v_i,b_i)$. A partition plan is valid if and only if for every constraint, region $u_i$ does not belong to country $a_i$ **or** region $v_i$ does not belong to country $b_i$. Here **or** is logical OR. Dream guarantees that there is at least one valid partition plan. You need to construct a valid partition plan.

The first line contains two positive integers $n$ and $m$. The next $m$ lines each contain four positive integers $u_i,a_i,v_i,b_i$.

Output a string of length $n$. The $i$-th character of the string is the country that region $i$ belongs to.

#### Sample 1 Explanation 23322, 23332, and 23333 are all valid plans. #### Constraints For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 10^6$. For specific properties, please refer to the input testdata yourself. [Click here to download the input data.](https://gitee.com/w33z8kqrqk8zzzx33/dream-oi-extra/raw/master/down.zip) If the download link above does not work, see this one below: Link: https://pan.baidu.com/s/1D3ytb0626EKZ_emw3gLwVQ Extraction code: inbj #### Notes [Minecraft OI Round 4](https://www.luogu.com.cn/contest/33344) Extra Idea & solution: w33z8kqrqk8zzzx33. Check: tiger2005. Translated by ChatGPT 5